QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#369693#8513. Insects, Mathematics, Accuracy, and Efficiencywillow#WA 1ms4748kbC++176.7kb2024-03-28 16:33:082024-03-28 16:33:08

Judging History

你现在查看的是最新测评结果

  • [2024-03-28 16:33:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4748kb
  • [2024-03-28 16:33:08]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9, pi = acos(-1);
int Dcmp(double x) {
    return x < -eps ? -1 : x > eps ? 1 : 0;
}
double Sqr(double x) {
    return x * x;
}
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    bool operator < (const Point &rhs) const {
        return Dcmp(x - rhs.x) == 0 ? Dcmp(y - rhs.y) < 0 : Dcmp(x - rhs.x) < 0;
    }
    Point operator + (const Point &rhs) const {
        return Point(x + rhs.x, y + rhs.y);
    }
    Point operator - (const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }
    double operator * (const Point &rhs) const {
        return x * rhs.x + y * rhs.y;
    }
    double operator ^ (const Point &rhs) const {
        return x * rhs.y - y * rhs.x;
    }
    Point operator * (const double &k) const {
        return Point(x * k, y * k);
    }
    Point operator / (const double &k) const {
        return Point(x / k, y / k);
    }
    double len2() {
        return x * x + y * y;
    }
    double len() {
        return sqrt(len2());
    }
    Point Unit() {
        return *this / len();
    }
    Point Rotate90() {
        return Point(-y, x);
    }
};
int Left(Point a, Point b, Point c) {
    return Dcmp((b - a) ^ (c - a)) >= 0;
}
double Area(Point a, Point b, Point c) {
    return fabs((c - a) ^ (b - a)) / 2;
}
Point base;
vector<Point> Convex(vector<Point> a) {
    int n = a.size(), cnt = 0;
    if(n < 3)
        return a;
    base = a[0];
    for(auto p : a) if(p < base) base = p;
    sort(a.begin(), a.end(), [](const Point &a, const Point &b) {
        int d = Dcmp((a - base) ^ (b - base));
        return d ? d > 0 : Dcmp((a - base).len() - (b - base).len()) < 0;
    });
    vector<Point> res;
    for(int i = 0; i < n; ++ i) {
        while(cnt > 1 && Left(res[cnt - 2], a[i], res[cnt - 1]))
            -- cnt, res.pop_back();
        res.push_back(a[i]), ++ cnt;
    }
    return res;
}
struct Line {
    Point s, t;
    Line(Point s = Point(), Point t = Point()) : s(s), t(t) {}
};
double DisToLine(Line l, Point p) {
    Point v1 = l.t - l.s, v2 = p - l.s;
    return fabs(v1 ^ v2) / v1.len();
}
Point LineInter(Line l1, Line l2) {
    double a1 = (l2.t - l2.s) ^ (l1.s - l2.s), a2 = (l2.t - l2.s) ^ (l1.t - l2.s);
    return (l1.s * a2 - l1.t * a1) / (a2 - a1);
}
Point LineVer(Line l, Point p) {
    Point v = l.t - l.s;
    v = v.Rotate90();
    return LineInter(l, Line(p, p + v));
}
struct Circle {
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
};
vector<Point> LineInterCircle(Line a, Circle b) {
    if(Dcmp(DisToLine(a, b.c) - b.r) > 0)
        return vector<Point>();
    if(Dcmp(DisToLine(a, b.c) - b.r) == 0)
        return {LineVer(a, b.c)};
    double x = sqrt(Sqr(b.r) - Sqr(DisToLine(a, b.c)));
    Point o = LineVer(a, b.c);
    return {o - (a.t - a.s).Unit() * x, o + (a.t - a.s).Unit() * x};
}
int n, r;
vector<Point> p;
const int maxn = 2e4 + 5;
double le[maxn], ri[maxn];
Point cp[maxn];
vector<pair<double, int> > op;
set<int> s;
double Calc(double al, double ar, Point a, Point b) {
// cerr << "Get Calc(" << al << ", " << ar << ") P(" << a.x << ", " << a.y << ") P(" << b.x << ", " << b.y << ")" << endl;
    for(int i = 1; i <= 100; ++ i) {
        double ml = al + (ar - al) / 3, mr = ar - (ar - al) / 3;
        Point pl = Point(r * cos(ml), r * sin(ml)), pr = Point(r * cos(mr), r * sin(mr));
        if(Dcmp(Area(a, b, pl) - Area(a, b, pr)) > 0)
            ar = mr;
        else
            al = ml;
    }
    Point pl = Point(r * cos(al), r * sin(al)), pr = Point(r * cos(ar), r * sin(ar));
    return max(Area(a, b, pl), Area(a, b, pr));
}
int main() {
    scanf("%d%d", &n, &r);
    for(int i = 1, x, y; i <= n; ++ i) {
        scanf("%d%d", &x, &y);
        p.push_back(Point(x, y));
    }
    if(n == 1) {
        puts("0.0");
        return 0;
    }
    auto c = Convex(p);
    int m = c.size();
    double area = 0;
    for(int i = 0; i < m; ++ i) {
        int j = (i + 1) % m;
        area += Area(c[0], c[i], c[j]);
        auto in = LineInterCircle(Line(c[i], c[j]), Circle(Point(0, 0), r));
        assert(in.size() == 2u);
        double al = atan2(in[0].y, in[0].x), ar = atan2(in[1].y, in[1].x);
        if(Dcmp(al - ar) > 0)
            al -= 2 * pi;
        cp[i] = c[i];
        le[i] = al;
        ri[i] = ar;
    }
// cerr << "Fuck" << endl;
    for(int i = 0; i < m; ++ i) {
        cp[i + m] = cp[i];
        le[i + m] = le[i] + 2 * pi;
        ri[i + m] = ri[i] + 2 * pi;
    }
    for(int i = 0; i < 2 * m; ++ i) {
        op.push_back({le[i], -(i + 1)});
        op.push_back({ri[i], i + 1});
    }
// cerr << "?????" << endl;
    sort(op.begin(), op.end());
    int sop = op.size();
    double nowa = 0, ans = area;
    for(int i = 0; i < sop; ) {
        int j = i;
        while(j < sop && Dcmp(op[i].first - op[j].first) == 0) {
// cerr << op[j].first << " " << op[j].second << endl;
            if(op[j].second < 0) { // add
                int q = -(op[j].second + 1);
// cerr << "Add " << q << endl;
                if(s.size() > 0) {
                    int w = *s.begin();
                    nowa += Area(cp[w], cp[q], cp[(q + 1) % (2 * m)]);
                }
                s.insert(q);
            }
            else {
                int q = op[j].second - 1;
// cerr << "Del " << q << endl;
                if(s.size() > 0) {
                    int w = *prev(s.end());
                    nowa -= Area(cp[q], cp[(q + 1) % (2 * m)], cp[(w + 1) % (2 * m)]);
                }
                s.erase(s.find(q));
            }
// cerr << "? " << j << endl;
            ++ j;
        }
// cerr << "Fuck " << i << " " << j << endl;
        assert(s.size());
        if(*s.begin() >= m) {
            break;
        }
// cerr << "Set: ";
// for(auto x : s)
//     cerr << x << " ";
// cerr << endl;
        double mx = Calc(op[i].first, op[j].first, cp[*s.begin()], cp[(*prev(s.end()) + 1) % (2 * m)]);
// cerr << area << " " << mx << " " << nowa << " " << area + mx - nowa << endl;
        ans = max(ans, area + mx - nowa);
        i = j;
    }
    printf("%.15f\n", ans);
}
/*
Fuck
?????
-3.14159 -1
Add 0
? 0
Fuck 0 1
Set: 0 
Get Calc(-3.14159, -1.5708) P(0, 0) P(1, 0)
2e+06 1 0 2e+06
-1.5708 1
Del 0
? 1
-1.5708 -2
Add 1
? 2
Fuck 1 3
Set: 1 
Get Calc(-1.5708, -1.13687e-16) P(1, 0) P(2, 0)
2e+06 1 0 2e+06
-1.13687e-16 2
Del 1
? 3
0 -3
Add 2
? 4
Fuck 3 5
Set: 2 
Get Calc(-1.13687e-16, 3.14159) P(2, 0) P(3, 0)
2e+06 1 0 2e+06
3.14159 -4
Add 3
? 5
3.14159 3
Del 2
? 6
Fuck 5 7
2000001.000000000000000
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4556kb

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:

1999999.999999998137355

result:

ok found '1999999.999999998', expected '2000000.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4556kb

input:

2 100
17 7
19 90

output:

4849.704644436478702

result:

ok found '4849.704644436', expected '4849.704644438', error '0.000000000'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4132kb

input:

1 100
13 37

output:

0.0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 4748kb

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

2039999.999999998137355

result:

wrong answer 1st numbers differ - expected: '2240000.0000000', found: '2040000.0000000', error = '0.0892857'