# 题解 | #J、Distance to Work#

J、Distance to Work

https://ac.nowcoder.com/acm/problem/17249

``````using namespace std;
const int MAX=1e6+10;
const int MOD=998244353;
const double PI=acos(-1.0);
typedef long long ll;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
void show(){cout<<"("<<x<<","<<y<<")"<<endl;}
}a[300],b[300];
Point operator+(Point A,Point B){return (Point){A.x+B.x,A.y+B.y};}        //向量A+B
Point operator-(Point A,Point B){return (Point){A.x-B.x,A.y-B.y};}        //向量A-B
Point operator*(Point A,double B){return (Point){A.x*B,A.y*B};}           //向量A*B
Point operator/(Point A,double B){return (Point){A.x/B,A.y/B};}           //向量A/B
double operator*(Point A,Point B){return A.x*B.x+A.y*B.y;}            //向量A B的点积
double operator^(Point A,Point B){return A.x*B.y-A.y*B.x;}            //向量A B的叉积
double cross(Point A,Point B){return A.x*B.y-A.y*B.x;}                //向量A B的叉积
double dis(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}//A B两点的距离
double dis2(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}     //A B两点的距离的平方
double Polyarea(Point *p,int n)   //求多边形面积(任意形状都可)
{
double area=0;
for(int i=1;i<n-1;i++)area+=(p[i]-p[0])^(p[i+1]-p[0]);
return fabs(area/2);
}
double Distoline(Point P,Point A,Point B){return fabs(cross(B-A,P-A))/dis(A,B);}//点P到直线AB距离
Point pverti(Point P,Point A,Point B)//求点P在直线AB上的投影点
{
double AA=A.y-B.y;
double BB=-(A.x-B.x);
double CC=A.y*(A.x-B.x)-A.x*(A.y-B.y);
Point PP=(Point){P.x-2*AA*(AA*P.x+BB*P.y+CC)/(AA*AA+BB*BB),P.y-2*BB*(AA*P.x+BB*P.y+CC)/(AA*AA+BB*BB)};
return (PP+P)/2;
}
double slove(Point P,Point A,Point B,double R)
{
double h=Distoline(P,A,B);
if(dis2(P,A)<=R*R&&dis2(P,B)<=R*R)return fabs(cross(A-P,B-P))/2;//A B两点均在圆内
if(dis2(P,A)>R*R)swap(A,B);
if(dis2(P,A)<=R*R&&dis2(P,B)>R*R)                               //A B两点有一点在圆内
{
double angle=(dis2(P,A)+dis2(A,B)-dis2(P,B))/(2*dis(P,A)*dis(A,B));
angle=acos(angle);
double C=angle+asin(sin(angle)*dis(P,A)/R);
double len=sin(C)*R/sin(angle);
angle=(dis2(P,A)+dis2(P,B)-dis2(A,B))/(2*dis(P,A)*dis(P,B));
angle=acos(angle)-(PI-C);
return len*h/2+angle*R*R/2;
}
double angle=(dis2(P,A)+dis2(P,B)-dis2(A,B))/(2*dis(P,A)*dis(P,B));//A B两点均在圆外
double area=acos(angle)*R*R/2;
Point PP=pverti(P,A,B);
if(h>=R||cross(PP-P,A-P)*cross(PP-P,B-P)>0)return area;            //线段AB与圆不相交
return area-(2*acos(h/R)*R*R/2-h*sqrt(R*R-h*h));                   //线段AB与圆相交
}
double cal(int n,Point p,double r)
{
double tot=0;
for(int i=0;i<n;i++)
{
if(cross(a[i]-p,a[(i+1)%n]-p)==0)continue;
double area=slove(p,a[i],a[(i+1)%n],r);
if(cross(a[i]-p,a[(i+1)%n]-p)>0)tot+=area;
else tot-=area;
}
return fabs(tot);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
double sum=Polyarea(a,n);
int m;
cin>>m;
for(int i=1;i<=m;i++)
{
int x,y,p,q;
scanf("%d%d%d%d",&x,&y,&p,&q);
p=q-p;
double l=0,r=1e9;
for(int i=1;i<=100;i++)
{
double mid=(l+r)/2;
if(cal(n,(Point){x*1.0,y*1.0},mid)<=sum*p/q)l=mid;
else r=mid;
}
printf("%.12lf\n",(l+r)/2);
}
return 0;
}
``````