QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243917#876. Big BrotherJooDdaeWA 63ms8368kbC++202.6kb2023-11-08 19:16:012023-11-08 19:16:02

Judging History

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

  • [2023-11-08 19:16:02]
  • 评测
  • 测评结果:WA
  • 用时:63ms
  • 内存:8368kb
  • [2023-11-08 19:16:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

using point = array<ld, 2>;
using line = array<point, 2>;

static const ld eps = 1e-13;

ld solve(const vector<point> &p){
    auto plus = [&](point p, point q)->point{
        return {p[0] + q[0], p[1] + q[1]};
    };
    auto minus = [&](point p, point q)->point{
        return {p[0] - q[0], p[1] - q[1]};
    };
    auto dot = [&](point p, point q)->ld{
        return p[0] * q[0] + p[1] * q[1];
    };
    auto mul = [&](ld c, point p)->point{
        return {p[0] * c, p[1] * c};
    };
    auto cross = [&](point p, point q)->ld{
        return p[0] * q[1] - p[1] * q[0];
    };
    auto inter = [&](line s, line t)->point{
        ld alpha = cross(minus(t[0], s[0]), t[1]) / cross(s[1], t[1]);
        return plus(s[0], mul(alpha, s[1]));
    };

    int n = p.size();
    vector<line> hps(n);
    for(int i=0;i<n;i++) hps[i] = {p[(i+1)%n], minus(p[i], p[(i+1)%n])};

    sort(hps.begin(), hps.end(), [&](line a, line b) { 
        ld aang = atan2l(a[1][1], a[1][0]), bang = atan2l(b[1][1], b[1][0]);
        if(aang != bang) return aang < bang;

        line c = line({point({0, 0}), point({a[1][1], a[1][0]})});
        ld cang = atan2l(c[1][1], c[1][0]);
        point A = inter(c, a), B = inter(c, b);

        point C = b[0];
        C[0] -= b[1][0] * 14124;
        C[1] -= b[1][1] * 14124;
        return cross(minus(B, C), minus(A, C)) > 0;
    });

    auto bad = [&](line l, line m, line n)->bool{
        auto s = cross(l[1], m[1]);
        if(abs(s) < eps) return false;
        auto p = cross(n[1], minus(plus(mul(s, l[0]), mul(cross(minus(m[0], l[0]), m[1]), l[1])), mul(s, n[0])));
        return s > 0 ? p <= eps : p >= -eps;
    };

    deque<line> dq;
    for(auto p: hps){
        if(!dq.empty() && abs(cross(dq.back()[1], p[1])) <= eps) continue;
        while((int)dq.size() >= 2 && bad(dq[(int)dq.size() - 2], dq.back(), p)) dq.pop_back();
        while((int)dq.size() >= 2 && bad(dq[0], dq[1], p)) dq.pop_front();
        if((int)dq.size() < 2 || !bad(dq.back(), p, dq.front())) dq.push_back(p);
    }

    if(dq.size() < 3) return 0;

    int N = dq.size();
    vector<point> np(N);
    for(int i=0;i<N;i++) np[i] = inter(dq[i], dq[(i+1)%N]);

    ld re = 0;
    for(int i=0;i<N;i++) re += cross(np[i], np[(i+1)%N]);
    return abs(re)/2;
}


int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(15);
     
    int n; cin >> n;
    vector<point> p(n);
    for(auto &[x, y] : p) cin >> x >> y;
    cout << solve(p);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

8
0 0
0 1
1 1
1 2
2 2
2 1
3 1
3 0

output:

1.000000000000000

result:

ok "1.000000000"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

8
0 0
0 2
1 2
1 1
2 1
2 2
3 2
3 0

output:

0.000000000000000

result:

ok "0.000000000"

Test #3:

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

input:

6
140 62
97 141
68 156
129 145
153 176
130 109

output:

48.803495002058103

result:

ok "48.803495002"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

3
198 165
322 122
242 84

output:

4076.000000000000000

result:

ok "4076.000000000"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

15
0 250
30 250
125 250
180 250
250 250
250 100
250 80
250 0
140 0
100 0
73 0
0 0
0 2
0 30
0 90

output:

62500.000000000000000

result:

ok "62500.000000000"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

16
146 145
109 229
139 301
164 385
221 433
309 419
405 420
447 369
501 308
498 229
471 150
456 75
391 39
308 47
227 39
166 73

output:

114711.364655995883794

result:

ok "114711.364655996"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3740kb

input:

6
160 210
200 210
200 300
280 300
200 170
200 80

output:

0.000000000000000

result:

ok "0.000000000"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

8
198 165
230 113
246 117
281 161
266 36
247 68
228 79
200 30

output:

63.702361250448232

result:

ok "63.702361250"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

14
198 165
274 226
258 318
297 348
339 309
372 360
336 265
347 203
388 161
346 123
306 155
293 87
261 112
242 84

output:

2189.001647913251940

result:

ok "2189.001647913"

Test #10:

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

input:

150
9956003 4338159
9912302 4099714
9868603 3861269
9803272 3631902
9737943 3402535
9725452 3366405
9712963 3330276
9696862 3286153
9680763 3242031
9604920 3061837
9529080 2881643
9480997 2784399
9432916 2687155
9193856 2313907
8954799 1940659
8617533 1583544
8280269 1226429
8207226 1165339
8134185 ...

output:

77922149990018.139389038085938

result:

ok "77922149990018.218750000"

Test #11:

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

input:

1000
9999605 4937170
9999012 4905760
9998421 4874350
9997433 4842949
9996447 4811549
9995065 4780163
9993685 4748778
9991908 4717412
9990134 4686047
9987963 4654706
9985795 4623366
9983230 4592055
9980668 4560744
9977710 4529467
9974755 4498191
9971405 4466954
9968057 4435718
9964314 4404526
9960574...

output:

78537708558541.989006042480469

result:

ok "78537708558542.031250000"

Test #12:

score: -100
Wrong Answer
time: 63ms
memory: 8368kb

input:

50000
10000000 4998743
9999998 4998115
9999999 4997487
9999998 4996858
9999999 4996230
9999997 4995601
9999997 4994973
9999995 4994345
9999996 4993717
9999994 4993088
9999994 4992460
9999992 4991832
9999992 4991204
9999990 4990575
9999990 4989947
9999987 4989318
9999987 4988690
9999984 4988062
99999...

output:

78539413955152.002204895019531

result:

wrong answer 1st numbers differ: expected 78539327974559.9375000000, found 78539413955152.0000000000, absolute error = 85980592.0625000000, error =   0.000001