萌新求问,过了90分,实在改不出来了QAQ
查看原帖
萌新求问,过了90分,实在改不出来了QAQ
291779
A_SOUL_Ava楼主2023/11/10 11:32
#include<bits/stdc++.h>

using namespace std;

const double eps = 1e-6;
const double PI = acos(-1);

struct point 
{
    double x, y;
};

double R;

point operator- (point a, point b)
{
    return {a.x - b.x, a.y - b.y};
}

point operator+ (point a, point b)
{
    return {a.x + b.x, a.y + b.y};
}

point operator* (point a, double t)
{
    return {a.x * t, a.y * t};
}

double operator* (point a, point b)
{
    return a.x * b.y - a.y * b.x;
}

point operator/ (point a, double t)
{
    return {a.x / t, a.y / t};
}

int sign(double a)
{
    if(fabs(a) < eps) return 0;
    if(a > 0) return 1;
    return -1;
}

int dcmp(double a, double b)
{
    if(fabs(a - b) < eps) return 0;
    if(a > b) return 1;
    return -1;
}

double dot(point a, point b)
{
    return a.x * b.x + a.y * b.y;
}

double cross(point a, point b)
{
    return a.x * b.y - a.y * b.x;
}

point rotate(point a, double b)
{
    return {a.x * cos(b) + a.y * sin(b), -a.x * sin(b) + a.y * cos(b)};
}

double get_dist(point a, point b)
{
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

point get_line_intersection(point p, point v, point q, point w)
{
    auto u = p - q;
    double t = w * u / (v * w);
    return p + v * t;
}

bool on_segment(point a, point b, point c)
{
    if(sign(dot(a - b, a - c)) <= 0 && sign(cross(a - b, a - c)) == 0) return true;
    return false;
}

point norm(point a)
{
    return a / sqrt(dot(a, a));
}

double get_circle_line_intersection(point a, point b, point &pa, point &pb)
{
    point C = {0, 0};
    auto e = get_line_intersection(a, b - a, C, rotate(b - a, PI / 2));
    auto mind = get_dist(C, e);
    if (!on_segment(e, a, b)) mind = min(get_dist(C, a), get_dist(C, b));
    if (dcmp(R, mind) <= 0) return mind;
    auto len = sqrt(R * R - get_dist(C, e) * get_dist(C, e));
    pa = e + norm(a - b) * len;
    pb = e + norm(b - a) * len;
    return mind;
}

double get_sector_area(point a, point b)
{
    point C = {0, 0};
    double th = acos(dot(a, b) / get_dist(C, a) / get_dist(C, b));
    if(cross(a, b) < 0) th = -th;
    return R * R / 2 * th;
}

double get_circle_line_triangle_area(point aa, point bb)
{
    point C = {0,0};
    if(dcmp(get_dist(C, aa), R) <= 0 && dcmp(get_dist(C, bb), R) <= 0)
        return cross(aa, bb) / 2;


    point pa, pb;
    double mind = get_circle_line_intersection(aa, bb, pa, pb);

    if(dcmp(mind, R) >= 0)
        return get_sector_area(aa, bb);


    if(dcmp(get_dist(aa, C), R) <= 0)
        return cross(aa, pb) / 2 + get_sector_area(pb, bb);

    if(dcmp(get_dist(bb, C), R) <= 0)
        return cross(pa, bb) / 2 + get_sector_area(aa, pa);

    return get_sector_area(aa, pa) + get_sector_area(pb, bb) + cross(pa, pb) / 2;

}

void perfect()
{
    int n;
        cin >> n;
        double S;
        cin >> S;
        vector<point> q(n + 5);
        double l = 0, r = 0;
        for(int i = 1; i <= n; i ++)
        {
            cin >> q[i].x >> q[i].y;
            r = max(r, get_dist(q[i], {0, 0}));
        }

        while(r - l > 1e-4)
        {
            double s = 0;
            R = (l + r) / 2;
            for(int i = 1; i <= n; i ++)
                s += get_circle_line_triangle_area(q[i], q[i % n + 1]);

            s = fabs(s);

            if(s <= S) l = R;
            else r = R;
        }

        printf("%.2lf\n", l);
}

int main()
{
    int T = 1;
    while(T --) perfect();
    return 0;
}
2023/11/10 11:32
加载中...