牛客网暑期ACM多校训练营（第三场）J 题解

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-7;
const double INF = 1e20;
const double pi = acos(-1.0);
int dcmp(double x)
{
    if (fabs(x) < eps) return 0;
    return (x < 0 ? -1 : 1);
}

inline double sqr(double x)
{
    return x * x;
}

struct Point
{
    double x, y;

    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}

    void input()
    {
        scanf("%lf%lf", &x, &y);
    }

    void output()
    {
        printf("%.2f %.2f\n", x, y);
    }

    bool operator==(const Point &b) const
    {
        return (dcmp(x - b.x) == 0 && dcmp(y - b.y) == 0);
    }

    bool operator<(const Point &b) const
    {
        return (dcmp(x - b.x) == 0 ? dcmp(y - b.y) < 0 : x < b.x);
    }

    Point operator+(const Point &b) const
    {
        return Point(x + b.x, y + b.y);
    }

    Point operator-(const Point &b) const
    {
        return Point(x - b.x, y - b.y);
    }

    Point operator*(double a)
    {
        return Point(x * a, y * a);
    }

    Point operator/(double a)
    {
        return Point(x / a, y / a);
    }

    double len2()  //返回长度的平方
    {
        return sqr(x) + sqr(y);
    }

    double len()  //返回长度
    {
        return sqrt(len2());
    }

    Point change_len(double r)  //转化为长度为r的向量
    {
        double l = len();
        if (dcmp(l) == 0) return *this;//零向量返回自身
        r /= l;
        return Point(x * r, y * r);
    }



};

double cross(Point a, Point b)  //叉积
{

    return a.x * b.y - a.y * b.x;
}

double dot(Point a, Point b)  //点积
{

    return a.x * b.x + a.y * b.y;
}

double dis(Point a, Point b)  //两个点的距离
{

    Point p = b - a;
    return p.len();
}

double rad(Point a, Point b)  //两个向量的夹角
{

    return fabs(atan2(fabs(cross(a, b)), dot(a, b)));
}


//************直线 线段
struct Line
{
    Point s, e;//直线的两个点
    Line() {}
    Line(Point _s, Point _e) : s(_s), e(_e) {}
    double length()  //求线段长度
    {
        return dis(s, e);
    }

};

double point_to_line(Point p, Line a)  //点到直线的距离
{
    return fabs(cross(p - a.s, a.e - a.s) / a.length());
}

Point projection(Point p, Line a)  //点在直线上的投影
{
    return a.s + (((a.e - a.s) * dot(a.e - a.s, p - a.s)) / (a.e - a.s).len2());
}

//***************圆
struct Circle
{
    //圆心 半径
    Point p;
    double r;

    Circle() {}

    Circle(Point _p, double _r) : p(_p), r(_r) {}

    Circle(double a, double b, double _r)
    {
        p = Point(a, b);
        r = _r;
    }

    void input()
    {
        p.input();
        scanf("%lf", &r);
    }

    void output()
    {
        p.output();
        printf(" %.2f\n", r);
    }

    bool operator==(const Circle &a) const
    {
        return p == a.p && (dcmp(r - a.r) == 0);
    }

    double area()  //面积
    {
        return pi * r * r;
    }

    double circumference()  //周长
    {
        return 2 * pi * r;
    }

    bool operator<(const Circle &a) const
    {
        return p < a.p || (p == a.p && r < a.r);
    }
};

int relation(Point p, Circle a)  //点和圆的关系
{
    //0:圆外 1:圆上 2:圆内
    double d = dis(p, a.p);
    if (dcmp(d - a.r) == 0) return 1;
    return (dcmp(d - a.r) < 0 ? 2 : 0);
}

int relation(Line a, Circle b)  //直线和圆的关系
{
    //0:相离 1:相切 2:相交
    double p = point_to_line(b.p, a);
    if (dcmp(p - b.r) == 0) return 1;
    return (dcmp(p - b.r) < 0 ? 2 : 0);
}


int line_cirlce_intersection(Line v, Circle u, Point &p1, Point &p2)  //直线和圆的交点
{
    //返回交点个数 交点保存在引用中
    if (!relation(v, u)) return 0;
    Point a = projection(u.p, v);
    double d = point_to_line(u.p, v);
    d = sqrt(u.r * u.r - d * d);
    if (dcmp(d) == 0)
    {
        p1 = a, p2 = a;
        return 1;
    }
    p1 = a + (v.e - v.s).change_len(d);
    p2 = a - (v.e - v.s).change_len(d);
    return 2;
}

double circle_traingle_area(Point a, Point b, Circle c)  //圆心三角形的面积
{
    //a.output (), b.output (), c.output ();
    Point p = c.p;
    double r = c.r; //cout << cross (p-a, p-b) << endl;
    if (dcmp(cross(p - a, p - b)) == 0) return 0;
    Point q[5];
    int len = 0;
    q[len++] = a;
    Line l(a, b);
    Point p1, p2;
    if (line_cirlce_intersection(l, c, q[1], q[2]) == 2)
    {
        if (dcmp(dot(a - q[1], b - q[1])) < 0) q[len++] = q[1];
        if (dcmp(dot(a - q[2], b - q[2])) < 0) q[len++] = q[2];
    }
    q[len++] = b;
    if (len == 4 && dcmp(dot(q[0] - q[1], q[2] - q[1])) > 0)
        swap(q[1], q[2]);
    double res = 0;
    for (int i = 0; i < len - 1; i++)
    {
        if (relation(q[i], c) == 0 || relation(q[i + 1], c) == 0)
        {
            double arg = rad(q[i] - p, q[i + 1] - p);
            res += r * r * arg / 2.0;
        }
        else
        {
            res += fabs(cross(q[i] - p, q[i + 1] - p)) / 2;
        }
    }
    return res;
}

double ComputeSignedArea(const vector<Point> &p)        //多边形面积 如果小于零，reverse(P.begin(), P.end());再调用一次 
{
    double area = 0;
    for (unsigned i = 0; i < p.size(); i++)
    {
        unsigned j = (i + 1) % p.size();
        area += p[i].x * p[j].y - p[j].x * p[i].y;
    }
    return area / 2.0;
}

double area_polygon_circle(Circle c, const vector<Point>& p)   //多边形与圆面积 
{
    double ans = 0;
    for (int i = 0; i < (int) p.size(); i++)
    {
        int j = (i + 1) % int(p.size());
        if (dcmp(cross(p[j] - c.p, p[i] - c.p)) >= 0)
            ans += circle_traingle_area(p[i], p[j], c);
        else
            ans -= circle_traingle_area(p[i], p[j], c);
    }
    return fabs(ans);
}


//上面是板子

vector<Point>polygon;        //存多边形的点 
int main()
{
    int n;cin>>n;
    for(int i=0;i<n;i++)
    {
        int x,y;scanf("%d%d",&x,&y);
        polygon.push_back(Point(x,y));
    }
    if (ComputeSignedArea(polygon) < 0)
    reverse(polygon.begin(), polygon.end());
    double totArea = ComputeSignedArea(polygon);
    int q;cin>>q;
    while(q--)
    {
        int x,y,p,q;
        cin>>x>>y>>p>>q;
        p=q-p;
        Point center=Point(x,y);        //圆 
        double l=eps/2,r=5e6;
        while(r-l>eps)
        {
            double mid=(l+r)*0.5;
            Circle c(center,mid);
            if(area_polygon_circle(c,polygon)/p>totArea/q)
            {
                r=mid;
            }
            else l=mid;
        }
        printf("%.12lf\n",l);
    }
    return 0;
}