QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#243924#876. Big BrotherJooDdaeWA 835ms50036kbC++202.6kb2023-11-08 19:18:312023-11-08 19:18:33

Judging History

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

  • [2023-11-08 19:18:33]
  • 评测
  • 测评结果:WA
  • 用时:835ms
  • 内存:50036kb
  • [2023-11-08 19:18:31]
  • 提交

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(abs(aang - bang) > eps) 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 = minus(b[0], mul(1557155715, b[1]));
        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: 3744kb

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: 1ms
memory: 3796kb

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: 0ms
memory: 3700kb

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: 3792kb

input:

3
198 165
322 122
242 84

output:

4076.000000000000000

result:

ok "4076.000000000"

Test #5:

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

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: 3740kb

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: 3680kb

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: 1ms
memory: 3792kb

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: 3800kb

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: 2ms
memory: 3920kb

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: 0
Accepted
time: 67ms
memory: 8412kb

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:

78539328042311.010902404785156

result:

ok "78539327974559.937500000"

Test #13:

score: 0
Accepted
time: 401ms
memory: 26976kb

input:

250000
10000000 4999749
9999999 4999623
10000000 4999497
9999999 4999371
10000000 4999246
9999999 4999120
10000000 4998995
9999999 4998869
10000000 4998743
9999999 4998617
10000000 4998492
9999999 4998366
10000000 4998241
9999999 4998115
10000000 4997989
9999998 4997863
9999999 4997738
9999998 49976...

output:

78525346698716.009788513183594

result:

ok "78525334096415.250000000"

Test #14:

score: -100
Wrong Answer
time: 835ms
memory: 50036kb

input:

500000
10000000 4999874
9999999 4999811
10000000 4999749
9999999 4999686
10000000 4999623
9999999 4999560
10000000 4999497
9999999 4999434
10000000 4999372
9999999 4999309
10000000 4999246
9999999 4999183
10000000 4999120
9999999 4999057
10000000 4998995
9999999 4998932
10000000 4998869
9999999 4998...

output:

78479129735991.933929443359375

result:

wrong answer 1st numbers differ: expected 78479009888752.7968750000, found 78479129735991.9375000000, absolute error = 119847239.1406250000, error =   0.000002