QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#709627#876. Big BrotherbecaidoAC ✓170ms42880kbC++203.7kb2024-11-04 15:57:122024-11-04 15:57:15

Judging History

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

  • [2024-11-04 15:57:15]
  • 评测
  • 测评结果:AC
  • 用时:170ms
  • 内存:42880kb
  • [2024-11-04 15:57:12]
  • 提交

answer

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << "\n";}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for(int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 5e5 + 5;

int n;

struct point {
    ll x = 0, y = 0;
    point() {}
    point(ll x, ll y) : x(x), y(y) {}
    point operator - (const point &o) const {
        return point(x - o.x, y - o.y);
    }
    ll operator * (const point &o) const {
        return x * o.y - y * o.x;
    }
    ll abs2() {
        return x * x + y * y;
    }
    void get() {
        cin >> x >> y;
    }
} p[SIZE];

struct Line {
    point X, Y;
    Line() {}
    Line(point X, point Y) : X(X), Y(Y) {}
};

int sign(ll x) {
    return x > 0 ? 1 : x < 0 ? -1 : 0;
}
int ori(point a, point b, point c) {
    return sign((b - a) * (c - a));
}
int cmp(point a, point b, bool same = true) {
    #define is_neg(k) (sign(k.y) < 0 || (sign(k.y) == 0 && sign(k.x) < 0))
    int A = is_neg(a), B = is_neg(b);
    if (A != B) return A < B;
    if (sign(a * b) == 0) return same ? a.abs2() < b.abs2() : -1;
    return sign(a * b) > 0;
}

pair<ll, ll> area_pair(Line a, Line b) {
    return pair<ll, ll>((a.Y - a.X) * (b.X - a.X), (a.Y - a.X) * (b.Y - a.X));
}
bool isin(Line l0, Line l1, Line l2) {
    auto [a02X, a02Y] = area_pair(l0, l2);
    auto [a12X, a12Y] = area_pair(l1, l2);
    if (a12X - a12Y < 0) a12X *= -1, a12Y *= -1;
    return (__int128) a02Y * a12X - (__int128) a02X * a12Y > 0;
}

vector<Line> halfPlaneInter(vector<Line> arr) {
    sort(arr.begin(), arr.end(), [&](Line a, Line b) ->int {
        if (cmp(a.Y - a.X, b.Y - b.X, 0) != -1) return cmp(a.Y - a.X, b.Y - b.X, 0);
        return ori(a.X, a.Y, b.Y) < 0;
    });
    deque<Line> dq(1, arr[0]);
    auto pop_back = [&](int t, Line p) {
        while (dq.size() >= t && !isin(p, dq[dq.size() - 2], dq.back())) dq.pop_back();
    };
    auto pop_front = [&](int t, Line p) {
        while (dq.size() >= t && !isin(p, dq[0], dq[1])) dq.pop_front();
    };
    for (auto p : arr) {
        if (cmp(dq.back().Y - dq.back().X, p.Y - p.X, 0) != -1) {
            pop_back(2, p);
            pop_front(2, p);
            dq.pb(p);
        }
    }
    pop_back(3, dq[0]), pop_front(3, dq.back());
    return vector<Line>(dq.begin(), dq.end());
}

pair<double, double> ints(point p1, point p2, point p3, point p4) {
    double a123 = (p2 - p1) * (p3 - p1);
    double a124 = (p2 - p1) * (p4 - p1);
    double x = (p4.x * a123 - p3.x * a124) / (a123 - a124);
    double y = (p4.y * a123 - p3.y * a124) / (a123 - a124);
    return {x, y};
}

void solve() {
    cin >> n;
    FOR (i, 1, n) p[i].get();
    reverse(p + 1, p + n + 1);
    vector<Line> v;
    FOR (i, 1, n - 1) v.pb(Line(p[i], p[i + 1]));
    v.pb(Line(p[n], p[1]));
    v = halfPlaneInter(v);
    if (v.size() <= 2) {
        cout << "0.00\n";
        return;
    }
    vector<pair<double, double>> ans;
    FOR (i, 0, v.size() - 2) ans.pb(ints(v[i].X, v[i].Y, v[i + 1].X, v[i + 1].Y));
    ans.pb(ints(v.back().X, v.back().Y, v[0].X, v[0].Y));
    double area = 0;
    ans.pb(ans[0]);
    FOR (i, 0, ans.size() - 2) {
        auto [x, y] = ans[i];
        auto [nx, ny] = ans[i + 1];
        area += x * ny - y * nx;
    }
    cout << fixed << setprecision(12) << abs(area / 2) << '\n';
}

int main() {
    Waimai;
    solve();
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 11692kb

input:

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

output:

1.000000000000

result:

ok "1.000000000"

Test #2:

score: 0
Accepted
time: 2ms
memory: 11612kb

input:

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

output:

0.00

result:

ok "0.000000000"

Test #3:

score: 0
Accepted
time: 3ms
memory: 11676kb

input:

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

output:

48.803495002059

result:

ok "48.803495002"

Test #4:

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

input:

3
198 165
322 122
242 84

output:

4076.000000000000

result:

ok "4076.000000000"

Test #5:

score: 0
Accepted
time: 2ms
memory: 11628kb

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.000000000000

result:

ok "62500.000000000"

Test #6:

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

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.364655995887

result:

ok "114711.364655996"

Test #7:

score: 0
Accepted
time: 2ms
memory: 11356kb

input:

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

output:

0.00

result:

ok "0.000000000"

Test #8:

score: 0
Accepted
time: 2ms
memory: 11848kb

input:

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

output:

63.702361250449

result:

ok "63.702361250"

Test #9:

score: 0
Accepted
time: 2ms
memory: 11708kb

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.001647913257

result:

ok "2189.001647913"

Test #10:

score: 0
Accepted
time: 2ms
memory: 11656kb

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.109375000000

result:

ok "77922149990018.218750000"

Test #11:

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

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:

78537708558542.000000000000

result:

ok "78537708558542.031250000"

Test #12:

score: 0
Accepted
time: 14ms
memory: 14448kb

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:

78539327974559.718750000000

result:

ok "78539327974559.937500000"

Test #13:

score: 0
Accepted
time: 59ms
memory: 26736kb

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:

78525334096415.359375000000

result:

ok "78525334096415.250000000"

Test #14:

score: 0
Accepted
time: 146ms
memory: 42480kb

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:

78479009888752.734375000000

result:

ok "78479009888752.796875000"

Test #15:

score: 0
Accepted
time: 3ms
memory: 11624kb

input:

150
9725000 5000000
9496052 4811560
9932639 4585795
9464516 4436001
9658831 4212018
9401664 4064398
9794486 3768986
9307937 3699357
9462178 3446106
9183994 3343440
9522050 2986654
9030702 2999142
9140549 2723714
8849139 2668879
9122960 2260712
8640576 2354967
8702951 2065077
8406477 2059608
8608394 ...

output:

11331974361764.552734375000

result:

ok "11331974361764.560546875"

Test #16:

score: 0
Accepted
time: 2ms
memory: 11800kb

input:

1000
9725000 5000000
9499911 4971726
9949609 4937799
9499200 4915183
9723507 4881261
9497779 4858652
9946482 4813434
9495648 4802144
9719032 4762596
9492806 4745667
9940232 4689187
9489256 4689230
9711575 4644081
9484996 4632843
9930861 4565137
9480028 4576513
9701143 4525791
9474353 4520250
9918375...

output:

302585512646.136718750000

result:

ok "302585512646.140625000"

Test #17:

score: 0
Accepted
time: 16ms
memory: 14052kb

input:

50000
9725000 5000000
9499999 4999435
9949999 4998756
9499999 4998304
9724999 4997625
9499999 4997173
9949998 4996268
9499998 4996042
9724997 4995250
9499997 4994911
9949996 4993780
9499995 4993780
9724994 4992875
9499993 4992649
9949992 4991292
9499992 4991518
9724990 4990500
9499989 4990387
994998...

output:

121175133.183593750000

result:

ok "121175133.132812500"

Test #18:

score: 0
Accepted
time: 68ms
memory: 26864kb

input:

250000
9725000 5000000
9499999 4999887
9949999 4999752
9499999 4999661
9724999 4999525
9499999 4999435
9949999 4999254
9499999 4999209
9724999 4999050
9499999 4998983
9949999 4998756
9499999 4998756
9724999 4998575
9499999 4998530
9949999 4998259
9499999 4998304
9724999 4998100
9499999 4998078
99499...

output:

4772368.080078125000

result:

ok "4772368.076171875"

Test #19:

score: 0
Accepted
time: 152ms
memory: 42768kb

input:

500000
9725000 5000000
9499999 4999944
9949999 4999876
9499999 4999831
9724999 4999763
9499999 4999718
9949999 4999627
9499999 4999605
9724999 4999525
9499999 4999492
9949999 4999378
9499999 4999378
9724999 4999288
9499999 4999265
9949999 4999130
9499999 4999152
9724999 4999050
9499999 4999039
99499...

output:

1169025.591796875000

result:

ok "1169025.593750000"

Test #20:

score: 0
Accepted
time: 3ms
memory: 11616kb

input:

72
4 50
4 51
5 56
6 60
7 63
9 68
10 70
13 75
15 78
18 82
19 83
23 86
26 88
31 91
33 92
38 94
41 95
45 96
50 97
51 97
56 96
60 95
63 94
68 92
70 91
75 88
78 86
82 83
83 82
86 78
88 75
91 70
92 68
94 63
95 60
96 56
97 51
97 50
96 45
95 41
94 38
92 33
91 31
88 26
86 23
83 19
82 18
78 15
75 13
70 10
68 ...

output:

6435.000000000000

result:

ok "6435.000000000"

Test #21:

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

input:

72
4 50
4 51
5 56
6 60
7 63
9 68
10 70
13 75
15 78
18 82
20 82
23 86
26 88
31 91
33 92
38 94
41 95
45 96
50 97
51 97
56 96
60 95
63 94
68 92
70 91
75 88
78 86
82 83
83 82
86 78
88 75
91 70
91 68
94 63
95 60
96 56
97 51
97 50
96 45
95 41
94 38
92 33
91 31
88 26
86 23
83 19
82 18
78 15
75 13
70 10
68 ...

output:

4180.100000000001

result:

ok "4180.100000000"

Test #22:

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

input:

336
10 500
10 501
11 512
12 522
13 531
14 539
15 546
16 552
18 563
19 568
21 577
22 581
25 592
27 599
30 609
31 612
35 623
38 631
40 636
43 643
47 652
52 663
53 665
59 676
64 685
68 692
71 697
76 705
83 716
85 719
92 729
97 736
105 747
108 751
115 760
119 765
128 776
133 782
139 789
146 797
154 806
...

output:

708179.000000000000

result:

ok "708179.000000000"

Test #23:

score: 0
Accepted
time: 2ms
memory: 11816kb

input:

336
10 500
10 501
11 512
12 522
13 531
14 539
15 546
16 552
18 563
19 568
21 577
22 581
25 592
27 599
30 609
31 612
35 623
38 631
40 636
43 643
47 652
52 663
53 665
59 676
64 685
68 692
71 697
76 705
83 716
85 719
92 729
97 736
105 747
109 750
115 760
119 765
128 776
133 782
139 789
146 797
154 806
...

output:

696280.075865801075

result:

ok "696280.075865801"

Test #24:

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

input:

1576
22 5000
22 5001
23 5026
24 5050
25 5073
26 5095
27 5116
28 5136
29 5155
30 5173
31 5190
32 5206
33 5221
34 5235
35 5248
37 5273
38 5285
40 5308
41 5319
43 5340
44 5350
46 5369
47 5378
49 5395
52 5420
53 5428
56 5451
58 5466
61 5488
62 5495
65 5515
67 5528
70 5547
74 5572
75 5578
79 5601
82 5618...

output:

73741747.000000000000

result:

ok "73741747.000000000"

Test #25:

score: 0
Accepted
time: 2ms
memory: 11820kb

input:

1576
22 5000
22 5001
23 5026
24 5050
25 5073
26 5095
27 5116
28 5136
29 5155
30 5173
31 5190
32 5206
33 5221
34 5235
35 5248
37 5273
38 5285
40 5308
41 5319
43 5340
44 5350
46 5369
47 5378
49 5395
52 5420
53 5428
56 5451
58 5466
61 5488
62 5495
65 5515
67 5528
70 5547
74 5572
75 5578
79 5601
82 5618...

output:

73705049.076299577951

result:

ok "73705049.076299563"

Test #26:

score: 0
Accepted
time: 4ms
memory: 11960kb

input:

7328
7 50000
7 50001
8 50056
9 50110
10 50163
11 50215
12 50266
13 50316
14 50365
15 50413
16 50460
17 50506
18 50551
19 50595
20 50638
21 50680
22 50721
23 50761
24 50800
25 50838
26 50875
27 50911
28 50946
29 50980
30 51013
31 51045
32 51076
33 51106
34 51135
35 51163
37 51218
38 51245
40 51298
41...

output:

7448951491.000000000000

result:

ok "7448951491.000000000"

Test #27:

score: 0
Accepted
time: 2ms
memory: 12016kb

input:

7328
7 50000
7 50001
8 50056
9 50110
10 50163
11 50215
12 50266
13 50316
14 50365
15 50413
16 50460
17 50506
18 50551
19 50595
20 50638
21 50680
22 50721
23 50761
24 50800
25 50838
26 50875
27 50911
28 50946
29 50980
30 51013
31 51045
32 51076
33 51106
34 51135
35 51163
37 51218
38 51245
40 51298
41...

output:

7448332528.534090995789

result:

ok "7448332528.534090042"

Test #28:

score: 0
Accepted
time: 11ms
memory: 15172kb

input:

33920
55 500000
55 500001
56 500119
57 500236
58 500352
59 500467
60 500581
61 500694
62 500806
63 500917
64 501027
65 501136
66 501244
67 501351
68 501457
69 501562
70 501666
71 501769
72 501871
73 501972
74 502072
75 502171
76 502269
77 502366
78 502462
79 502557
80 502651
81 502744
82 502836
83 5...

output:

741575176515.000000000000

result:

ok "741575176515.000000000"

Test #29:

score: 0
Accepted
time: 7ms
memory: 15104kb

input:

33920
55 500000
55 500001
56 500119
57 500236
58 500352
59 500467
60 500581
61 500694
62 500806
63 500917
64 501027
65 501136
66 501244
67 501351
68 501457
69 501562
70 501666
71 501769
72 501871
73 501972
74 502072
75 502171
76 502269
77 502366
78 502462
79 502557
80 502651
81 502744
82 502836
83 5...

output:

741573412548.757446289062

result:

ok "741573412548.757324219"

Test #30:

score: 0
Accepted
time: 35ms
memory: 31008kb

input:

157336
187 5000000
187 5000001
188 5000256
189 5000510
190 5000763
191 5001015
192 5001266
193 5001516
194 5001765
195 5002013
196 5002260
197 5002506
198 5002751
199 5002995
200 5003238
201 5003480
202 5003721
203 5003961
204 5004200
205 5004438
206 5004675
207 5004911
208 5005146
209 5005380
210 5...

output:

74106620545235.000000000000

result:

ok "74106620545235.000000000"

Test #31:

score: 0
Accepted
time: 38ms
memory: 32380kb

input:

157336
187 5000000
187 5000001
188 5000256
189 5000510
190 5000763
191 5001015
192 5001266
193 5001516
194 5001765
195 5002013
196 5002260
197 5002506
198 5002751
199 5002995
200 5003238
201 5003480
202 5003721
203 5003961
204 5004200
205 5004438
206 5004675
207 5004911
208 5005146
209 5005380
210 5...

output:

74103087971323.859375000000

result:

ok "74103087971323.890625000"

Test #32:

score: 0
Accepted
time: 3ms
memory: 11460kb

input:

1000
2600927 1831555
2984114 2324333
2787576 1961497
2689538 1755826
3028761 2094323
3008306 1946570
2887360 1607548
2631170 1248827
2470347 1030200
2599775 976740
2355502 478504
3115957 1757729
3013991 1652055
3820728 3275946
3463130 2975465
2475784 1734142
1806440 809618
1228787 158466
889070 1047...

output:

0.00

result:

ok "0.000000000"

Test #33:

score: 0
Accepted
time: 3ms
memory: 11640kb

input:

100
3929758 5668516
3749933 7186400
3671700 7927629
3735926 8648648
3696539 9488835
4063262 5499567
4098011 5704292
4139678 6088717
4070777 5280029
4228917 6549215
4520598 8419214
4828480 8246428
4211962 5750987
4483103 6401689
4610886 6564084
5813897 9050031
5230681 7607146
6109094 7997896
5521186 ...

output:

4397951.337890625000

result:

ok "4397951.332031250"

Test #34:

score: 0
Accepted
time: 2ms
memory: 11644kb

input:

339
9841560 4381918
5523440 4169860
9115892 4287496
8727198 4244767
5647505 4166184
6094829 4167703
8084370 4141154
8447161 4040556
7127522 4080692
9371627 3948065
8433750 3853008
8813865 3806327
5596744 4123253
9468765 3650496
8552072 3729494
7603308 3772657
9093114 3424080
6269139 3962293
5674235 ...

output:

32849.080078125000

result:

ok "32849.078125000"

Test #35:

score: 0
Accepted
time: 3ms
memory: 11836kb

input:

4063
499799 2678043
2533563 4266964
403464 2618451
1221250 3278868
105760 2429242
226632 2525041
215412 2517220
64334 2404256
2592208 4345606
811663 3027094
4044746 5463601
1404325 3485231
1786865 3771953
1076645 3252401
99034 2529000
3694400 5206336
2511697 4333861
73213 2556268
2066557 4031607
138...

output:

232.302734375000

result:

ok "232.306640625"

Test #36:

score: 0
Accepted
time: 8ms
memory: 12188kb

input:

20000
8066872 8602921
8232035 8787201
5776793 6015019
5878121 6129006
5025917 5167705
8660957 9266687
8658850 9263857
5327441 5507461
6546784 6882138
9179876 9850214
6853075 7226685
8949733 9588511
6930959 7311116
7507630 7960229
6399255 6711831
9080160 9728973
7405711 7844429
6878616 7249568
747610...

output:

0.074218750000

result:

ok "0.074218750"

Test #37:

score: 0
Accepted
time: 170ms
memory: 42880kb

input:

500000
953759 7297457
2580377 6153306
2634043 6115587
2839957 5970786
486723 7626180
2227022 6402004
1225883 7106390
139747 7870702
404456 7684670
1928896 6612075
549400 7583058
1773913 6721479
425016 7670854
2329665 6330471
465562 7642533
375055 7706403
601385 7547144
198343 7830881
359197 7717867
...

output:

0.001953125000

result:

ok "0.000000000"

Test #38:

score: 0
Accepted
time: 3ms
memory: 11804kb

input:

1000
1775807 6865631
4871886 8023283
7398086 8967646
143850 6312725
50868 6279999
4241424 7822696
22120 6286274
1098695 6682176
2064750 7034586
1875528 6981944
2387779 7184399
4969521 8131866
3585627 7642928
1961372 7069219
4352603 7948808
6407440 8673598
1789021 7127821
2036724 7247311
2738127 7483...

output:

5130.835937500000

result:

ok "5130.828125000"

Test #39:

score: 0
Accepted
time: 3ms
memory: 11800kb

input:

997
6923752 3142103
6035265 1166112
7134771 3679045
6503138 2357309
5554003 296869
6328294 2053182
5780625 885548
7317116 4249183
7819975 5401363
5642829 856378
7197673 4155115
7364650 4528812
6776562 3318236
5364427 497625
8844837 7590432
6698006 3244990
7640716 5174617
8857860 7626107
6979782 3911...

output:

5131.835937500000

result:

ok "5131.828125000"

Test #40:

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

input:

1000
9150738 1660620
8900040 3385771
9165624 1099746
9250879 361608
9026045 2195006
9016856 2243604
8908088 3047880
8641345 5262477
8796554 3843222
8898993 2719422
9033383 1282868
9110500 514669
8853009 2956351
9100138 459660
8690975 4209259
9048387 560131
8975462 1191225
8601171 5002153
8675233 419...

output:

29111.765625000000

result:

ok "29111.765625000"