Distance to Work (牛客多校) (圆和简单多边形相交面积 + 二分半径)

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9;            //浮点数精度控制
#define Vector point
#define Point point
const double PI = acos(-1);
struct Point{
    double x,y;
    Point(double x=0,double y=0) :x(x),y(y){}
    friend Vector operator + (Vector A,Vector B){ return Vector(A.x + B.x , A.y + B.y);}
    friend Vector operator - (Point A,Point B){ return Vector(A.x - B.x , A.y - B.y);}
    friend Vector operator * (Vector A,double p) {return Vector(A.x*p , A.y*p);}
    friend Vector operator / (Vector A,double p) {return Vector(A.x/p,A.y/p);}
    friend bool operator < (const Point &a,const Point &b){
    return a.x< b.x || ( a.x == b.x && a.y < b.y);
    }
};
int dcmp(double k){
    return k < -eps ?-1:k>eps?1:0;
}
double sqr(double k){return k*k;}
double mysqrt(double n){ return sqrt(max(0.0,n));}
double cross(Vector A,Vector B){return A.x*B.y - A.y*B.x;}
double dot(Vector A,Vector B){return A.x*B.x + A.y*B.y;}
double abs(Point o){return sqrt(dot(o,o));}
point _a[205],o;
int P,Q;
int n;
double r;
double ALL;
void circle_cross_line(Point a,Point b,Point o,double r,Point ret[],int &num){
    double x0 = o.x,y0 = o.y;
    double x1 = a.x,y1 = a.y;
    double x2 = b.x,y2 = b.y;
    double dx = x2 - x1,dy = y2-y1;
    double A = dx*dx +dy*dy;
    double B = 2*dx*(x1-x0)+2*dy*(y1-y0);
    double C = sqr(x1-x0)+sqr(y1-y0)-sqr(r);
    double delta = B*B - 4*A*C;
    num = 0;
    if(dcmp(delta)>=0){
    double t1 = (-B-mysqrt(delta))/(2*A);
    double t2 = (-B+mysqrt(delta))/(2*A);
    if(dcmp(t1-1)<=0 && dcmp(t1)>=0){
        ret[num++] = Point(x1+t1*dx , y1 + t1*dy);
    }
    if(dcmp(t2-1)<=0 && dcmp(t2)>=0){
        ret[num++] = Point(x1 + t2*dx,y1+t2*dy);
    }
    }

}
double sector_area(point a,point b){
    double theta = atan2(a.y,a.x) - atan2(b.y,b.x);
    while(theta <=0) theta+=2*PI;
    while(theta > 2*PI) theta -= 2*PI;
    theta = min (theta,2*PI - theta);
    return r*r *theta / 2;
}
double calc(Point a,Point b){
    Point p[2];
    int num = 0;
    int ina = dcmp(abs(a)-r)<0;
    int inb = dcmp(abs(b)-r)<0;
    if(ina){
    if(inb){
        return fabs(cross(a,b))/2.0;
    }else{
        circle_cross_line(a,b,Point(0,0),r,p,num);
        return sector_area(b,p[0])+fabs(cross(a,p[0]))/2.0;
    }
    }else{
    if(inb) {
        circle_cross_line(a,b,Point(0,0),r,p,num);
        return sector_area(p[0],a)+fabs(cross(p[0],b))/2.0;
    }else{
        circle_cross_line(a,b,Point(0,0),r,p,num);
        if(num == 2){
        return sector_area(a,p[0]) + sector_area(p[1],b)
            + fabs(cross(p[0],p[1]))/2.0;
        }else {
        return sector_area(a,b);
        }

    }
    }
}
double area(){
    double ret = 0;
    for(int i = 1;i<=n;i++){
    int sgn = dcmp(cross(_a[i],_a[i+1]));
    if(sgn!=0) ret+=sgn * calc(_a[i],_a[i+1]);
    }
    return abs(ret);
}
bool check()
{
    double are = area();
    if(dcmp(are - ALL)<0) return false;
    return true;
}
Point __a[206];
double PolygonArea(){
    double area = 0;
    for(int i = 2;i<n;i++)
    {
    area+=cross(__a[i] - __a[1],__a[i+1] - __a[1]);
    }    
    return fabs(area*0.5);
}
int main()
{
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>__a[i].x>>__a[i].y;
    __a[n+1] = __a[1];
    n++;
    int m;cin>>m;
    double all = PolygonArea();
    while(m--)
    {
         cin>>o.x>>o.y>>P>>Q;
        for(int i = 1;i<=n;i++) _a[i] = __a[i] - o;
        P = Q-P;
        ALL = P*all/Q;
        double L = 0,R = 5000000;
        while(dcmp(L-R)!=0)
        {
            r =(L+R)/2.0;
            if(check()) R = r;
            else L = r;
        }
        printf("%.10f\n",L);
    }
}