QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#549046#8861. Pollution SolutionGenshinImpactsFaultAC ✓1ms4324kbC++144.0kb2024-09-06 01:00:572024-09-06 01:00:58

Judging History

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

  • [2024-09-06 01:00:58]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4324kb
  • [2024-09-06 01:00:57]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ld = long double;
const ld eps = 1e-12;
const int N = 1010;
const ld PI = acosl(-1.0);
int n;
ld r;

struct Pld {
	ld x, y;
	Pld(ld X = 0, ld Y = 0) : x(X), y(Y) {}
	inline Pld operator+(const Pld &yy)const {
		return Pld(x + yy.x, y + yy.y);
	}
	inline Pld operator-(const Pld &yy)const {
		return Pld(x - yy.x, y - yy.y);
	}
	inline ld operator*(const Pld &yy)const {
		return x * yy.y - y * yy.x;
	}
	inline Pld operator*(const ld &yy)const {
		return Pld(x * yy, y * yy);
	}
	inline ld operator&(const Pld &yy)const {
		return x * yy.x + y * yy.y;
	}
	inline ld len() {
		return sqrtl(Pld(x, y) & Pld(x, y));
	}
	inline Pld norm() {
		return Pld(x / Pld(x, y).len(), y / Pld(x, y).len());
	}
}; Pld a[N];

struct Lld {
	Pld s, t;
	Lld(Pld S = Pld(), Pld T = Pld()) : s(S), t(T) {}
};

struct Cld {
	Pld c; ld r;
	Cld(Pld C = Pld(), ld R = 0) : c(C), r(R) {}
	bool in_circle(const Pld &x) { return (x - c).len() <= r; }
};

int sgn(ld x) {
	if(x > eps) return 1; if(x < -eps) return -1; return 0;
}
ld sqrl(ld x) { return x * x; }
ld point_to_line(Pld a, Lld b) {
	return fabsl((b.t - b.s) * (a - b.s)) / (b.t - b.s).len();
}
Pld project_to_line(Pld a, Lld b) {
	return b.s + (b.t - b.s) * (((a - b.s) & (b.t - b.s)) / ((b.t - b.s) & (b.t - b.s)));
}
bool point_on_segment(Pld a, Lld b) {
	return sgn((a - b.s) * (b.t - b.s)) == 0 && sgn((b.t - a) & (b.s - a)) <= 0;
}
vector<Pld> intersection(Cld x, Lld y) {
	if(point_to_line(x.c, y) > x.r) return {};
	ld xx = sqrtl(sqrl(x.r) - sqrl(point_to_line(x.c, y)));
	Pld a = project_to_line(x.c, y) - (y.s - y.t).norm() * xx;
	Pld b = project_to_line(x.c, y) + (y.s - y.t).norm() * xx;
	vector<Pld> vec;
	if(point_on_segment(a, y)) vec.push_back(a);
	if(point_on_segment(b, y)) vec.push_back(b);
	return vec;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cout.precision(20);
	cin >> n >> r;
	for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
	Cld cir = Cld(Pld(0, 0), r);
	int cur = cir.in_circle(a[1]);
	vector<pair<Pld, int> > vec;
	ld ans = 0;
	for(int u = 1; u <= n; u++) {
		int v = u % n + 1;
		int nxt = cir.in_circle(a[v]);
		if(cur == nxt && nxt == 0) {
			vector<Pld> pp = intersection(cir, Lld(a[u], a[v]));
			if(pp.size() == 2) {
				if((pp[0] - a[u]).len() > (pp[1] - a[u]).len()) swap(pp[1], pp[0]);
				ans += (pp[1].x + pp[0].x) * (pp[1].y - pp[0].y) * 0.5;
				vec.push_back({pp[0], 0});
				vec.push_back({pp[1], 1});
			}
			continue;
		}
		if(cur == nxt && nxt == 1) {
			// cout << "### " << cur << " " << nxt << "\n";
			// cout << ">>> " << a[u].x << " " << a[u].y << " -> " << a[v].x << " " << a[v].y << "\n";
			ans += (a[v].x + a[u].x) * (a[v].y - a[u].y) * 0.5;
			continue;
		}
		Pld tmp = intersection(cir, Lld(a[u], a[v]))[0];
		if(cur == 1) {
			// cout << "### " << cur << " " << nxt << "\n";
			// cout << ">>> " << a[u].x << " " << a[u].y << " -> " << tmp.x << " " << tmp.y << "\n";
			ans += (tmp.x + a[u].x) * (tmp.y - a[u].y) * 0.5;
		}
		else {
			// cout << "### " << cur << " " << nxt << "\n";
			// cout << ">>> " << tmp.x << " " << tmp.y << " -> " << a[v].x << " " << a[v].y << "\n";
			ans += (a[v].x + tmp.x) * (a[v].y - tmp.y) * 0.5;
		}
		vec.push_back({tmp, cur}), cur = nxt;
	}
	sort(vec.begin(), vec.end(), [](auto x, auto y) { return atan2(x.first.y, x.first.x) < atan2(y.first.y, y.first.x); });
	for(int i = 0; i < (int)vec.size(); i++) {
		if(vec[i].second != 1) {
			assert(vec[(i + 1) % (int)vec.size()].second == 1);
			continue;
		}
		assert(vec[(i + 1) % (int)vec.size()].second == 0);
		Pld p1 = vec[i].first, p2 = vec[(i + 1) % (int)vec.size()].first;
		// cout << "arc : " << p1.x << " " << p1.y << " -> " << p2.x << " " << p2.y << "\n";
		double t1 = atan2l(p1.y, p1.x);
		double t2 = atan2l(p2.y, p2.x);
		// cout << "$$$ " << t1 << " " << t2 << "\n";
		ans += 0.5 * r * r * (0.5 * sinl(2 * t2) + t2 - 0.5 * sinl(2 * t1) - t1);
	}
	cout << ans << "\n";
	return 0;
}

詳細信息

Test #1:

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

input:

6 10
-8 2
8 2
8 14
0 14
0 6
-8 14

output:

101.57643787179587071

result:

ok found '101.57644', expected '101.57644', error '0.00000'

Test #2:

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

input:

100 100
89 5
109 6
89 11
109 13
88 16
108 20
87 22
106 27
85 27
104 33
83 33
102 40
81 38
99 46
78 43
96 52
75 48
92 58
72 52
88 64
69 57
84 70
65 61
80 75
61 65
75 80
57 69
70 84
52 72
64 88
48 75
58 92
43 78
52 96
38 81
46 99
33 83
40 102
27 85
33 104
22 87
27 106
16 88
20 108
11 89
13 109
5 89
6 ...

output:

14459.588217587429892

result:

ok found '14459.58822', expected '14459.58822', error '0.00000'

Test #3:

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

input:

99 100
-120 1
110 2
-110 3
110 4
-110 5
110 6
-110 7
110 8
-110 9
110 10
-110 11
110 12
-110 13
110 14
-110 15
110 16
-110 17
110 18
-110 19
110 20
-110 21
110 22
-110 23
110 24
-110 25
110 26
-110 27
110 28
-110 29
110 30
-110 31
110 32
-110 33
110 34
-110 35
110 36
-110 37
110 38
-110 39
110 40
-1...

output:

7740.288953107498954

result:

ok found '7740.28895', expected '7740.28895', error '0.00000'

Test #4:

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

input:

100 150
-250 2
248 2
248 118
-248 118
-248 116
246 116
246 4
-246 4
-246 6
244 6
244 114
-244 114
-244 112
242 112
242 8
-242 8
-242 10
240 10
240 110
-240 110
-240 108
238 108
238 12
-238 12
-238 14
236 14
236 106
-236 106
-236 104
234 104
234 16
-234 16
-234 18
232 18
232 102
-232 102
-232 100
230...

output:

18064.620941504486606

result:

ok found '18064.62094', expected '18064.62094', error '0.00000'

Test #5:

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

input:

50 1000
-733 669
-616 650
-794 732
-1133 854
-1267 1007
-29 1221
445 1190
527 1059
549 917
1095 1320
777 799
678 739
1239 340
806 500
403 335
301 435
532 105
1241 42
813 458
1181 131
1234 183
1271 293
1263 664
1392 958
1421 773
1500 168
1432 1288
972 562
1292 1130
1336 1354
885 1373
-75 1314
70 1295...

output:

482487.84019330145708

result:

ok found '482487.84019', expected '482487.84019', error '0.00000'

Test #6:

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

input:

80 1000
-50 101
199 0
302 26
702 460
501 260
639 526
936 918
499 21
545 20
526 42
999 6
968 981
862 1192
343 363
576 806
804 1411
253 311
213 773
283 988
403 1084
485 1130
333 700
564 1190
164 939
640 1291
770 1412
686 1493
72 1412
-72 1327
-46 469
3 861
30 1000
121 1063
-38 437
-539 623
-440 737
-4...

output:

864123.10226932684498

result:

ok found '864123.10227', expected '864123.10227', error '0.00000'

Test #7:

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

input:

90 1000
-684 518
-693 140
-46 85
-361 152
278 434
35 182
627 653
312 264
358 65
237 245
2 56
488 62
452 115
631 30
425 134
765 297
985 393
972 543
755 629
787 569
706 535
708 533
661 526
461 431
968 790
207 516
990 801
846 1394
709 1461
766 1414
953 899
691 1087
771 1162
735 1371
584 847
-93 833
16 ...

output:

712192.8827510995161

result:

ok found '712192.88275', expected '712192.88275', error '0.00000'

Test #8:

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

input:

100 1000
10 1131
-195 913
-758 803
227 512
-304 371
76 425
315 444
772 171
370 631
878 82
325 275
247 179
-483 294
-220 565
-589 505
-748 574
-143 606
-802 618
-837 389
-611 377
-995 80
-420 245
-142 159
34 128
-597 317
493 68
956 43
935 664
993 483
987 773
958 1069
739 704
960 1044
887 900
739 351
...

output:

675234.66469876947065

result:

ok found '675234.66470', expected '675234.66470', error '0.00000'

Test #9:

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

input:

60 1000
407 330
795 140
949 259
942 604
679 458
872 1103
622 1233
1290 1257
1222 1132
1202 1191
848 917
1203 1157
1221 365
1498 1186
1310 1401
300 1327
277 848
471 1154
576 845
415 1032
124 338
-278 609
-470 570
119 754
-28 1193
-138 1013
-124 877
-591 1161
-121 854
-697 787
-1048 769
-1183 866
-133...

output:

826872.70671302486585

result:

ok found '826872.70671', expected '826872.70671', error '0.00000'

Test #10:

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

input:

70 1000
1376 577
1433 747
1194 105
1175 137
276 195
361 172
409 153
-283 110
-623 149
-678 314
442 577
255 427
321 540
-136 404
-163 306
467 400
867 513
-120 192
1387 655
981 849
993 870
1438 925
1440 403
1475 77
1471 908
1461 1325
394 394
1053 1212
1486 1344
963 1484
951 1321
1240 1345
275 912
6 86...

output:

856134.16356233357686

result:

ok found '856134.16356', expected '856134.16356', error '0.00000'

Test #11:

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

input:

80 1000
-594 599
-968 947
-966 1012
-936 1075
-848 1025
-565 1133
-916 1143
331 1227
706 568
805 763
833 858
1002 562
1127 181
325 725
384 662
519 486
-56 928
289 800
547 781
240 1125
112 1108
-51 1048
229 1185
-781 783
2 272
-194 127
1097 110
-254 562
-432 640
873 193
997 164
-366 732
-280 805
1197...

output:

825504.64925056957765

result:

ok found '825504.64925', expected '825504.64925', error '0.00000'

Test #12:

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

input:

90 1000
-1025 202
-530 86
76 123
-769 32
-496 20
961 73
1458 149
1367 444
209 319
964 389
1023 338
-63 253
-595 265
275 896
403 502
154 698
97 765
-401 400
-175 384
-290 322
1100 477
1285 597
1066 584
1463 927
902 760
1155 948
1290 924
907 1443
1162 1139
1135 1280
1178 1494
988 1498
855 1497
-134 14...

output:

948946.685091803185

result:

ok found '948946.68509', expected '948946.68509', error '0.00000'

Test #13:

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

input:

100 1000
-1258 519
-1363 1005
-1220 1204
-1248 828
-1245 562
-855 917
-1056 746
-771 1095
44 1249
-225 1152
826 1327
524 1197
674 1165
1346 1431
686 1361
774 1320
-67 1357
-175 1388
61 1393
1013 1431
-68 1371
864 1383
1128 1433
-371 1436
149 1487
395 1476
274 1500
-1451 1349
38 1429
-315 1367
-106 1...

output:

757050.30152154143207

result:

ok found '757050.30152', expected '757050.30152', error '0.00000'

Test #14:

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

input:

50 1000
-846 656
-765 389
-655 28
-699 496
468 896
380 850
-218 613
-93 594
828 999
176 592
24 518
148 645
-552 310
-575 221
942 356
389 465
798 464
529 620
789 719
563 666
813 745
937 861
187 563
202 551
-164 360
126 566
982 965
639 1171
953 1065
798 1421
594 1248
423 1309
-297 1144
122 1381
-378 1...

output:

543527.08515243686332

result:

ok found '543527.08515', expected '543527.08515', error '0.00000'

Test #15:

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

input:

60 1000
171 508
-110 699
-267 878
-49 817
620 443
513 428
240 608
529 194
770 228
942 562
637 888
927 734
860 1036
-447 875
237 962
648 1025
481 1015
-758 1141
-423 1158
218 1187
-140 1159
752 1103
395 1289
784 1242
894 1167
944 1271
890 1419
482 1318
163 1428
-663 1350
-821 1327
-672 1316
56 1246
1...

output:

801798.91627097747221

result:

ok found '801798.91627', expected '801798.91627', error '0.00000'

Test #16:

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

input:

70 1000
409 856
378 587
144 1220
-75 1104
-174 1106
-444 796
-427 647
-588 514
-583 787
-865 380
-803 294
-803 215
-899 313
-880 58
-485 87
-320 113
-524 324
-361 405
-341 581
-143 741
93 531
-13 395
-71 303
-368 242
-142 63
-740 13
-5 64
34 399
109 203
67 137
242 307
107 245
540 573
407 977
532 101...

output:

789666.06220459056192

result:

ok found '789666.06220', expected '789666.06220', error '0.00000'

Test #17:

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

input:

8 65
70 25
70 39
-70 39
-70 52
70 52
70 60
-75 60
-75 25

output:

2101.5994078402682561

result:

ok found '2101.59941', expected '2101.59941', error '0.00000'

Test #18:

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

input:

8 65
64 18
48 46
46 48
11 68
-11 68
-46 48
-48 46
-64 18

output:

4305.2765817915714104

result:

ok found '4305.27658', expected '4305.27658', error '0.00000'

Test #19:

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

input:

20 65
75 25
75 75
-75 75
-75 25
-10 25
-10 39
-70 39
-70 52
-10 52
-10 60
-70 60
-70 70
70 70
70 60
10 60
10 52
70 52
70 39
10 39
10 25

output:

1661.5994078402682561

result:

ok found '1661.59941', expected '1661.59941', error '0.00000'

Test #20:

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

input:

6 65
0 85
85 0
91 0
0 91
-91 0
-85 0

output:

309.59940784026825605

result:

ok found '309.59941', expected '309.59941', error '0.00000'

Test #21:

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

input:

8 65
-71 22
61 58
43 20
77 30
77 60
-39 60
-39 39
-71 39

output:

1680.0994078402682561

result:

ok found '1680.09941', expected '1680.09941', error '0.00000'

Test #22:

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

input:

8 65
71 39
39 39
39 60
-77 60
-77 30
-43 20
-61 58
71 22

output:

1680.0994078402682559

result:

ok found '1680.09941', expected '1680.09941', error '0.00000'

Test #23:

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

input:

4 65
66 25
31 60
-31 60
-66 25

output:

3284.5994078402682561

result:

ok found '3284.59941', expected '3284.59941', error '0.00000'

Test #24:

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

input:

9 65
46 70
-38 70
-38 53
-66 25
74 25
74 33
-36 63
11 68
46 48

output:

2720.5994078402682552

result:

ok found '2720.59941', expected '2720.59941', error '0.00000'

Test #25:

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

input:

9 65
-46 48
-11 68
36 63
-74 33
-74 25
66 25
38 53
38 70
-46 70

output:

2720.5994078402682552

result:

ok found '2720.59941', expected '2720.59941', error '0.00000'

Test #26:

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

input:

6 10
-8 2
8 2
8 14
0 14
0 6
-8 14

output:

101.57643787179587071

result:

ok found '101.57644', expected '101.57644', error '0.00000'

Test #27:

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

input:

3 20
-20 1
20 2
9 18

output:

325.47188656202169282

result:

ok found '325.47189', expected '325.47189', error '0.00000'

Test #28:

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

input:

3 20
8 18
-17 10
19 1

output:

256.5

result:

ok found '256.50000', expected '256.50000', error '0.00000'

Test #29:

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

input:

3 20
0 30
15 15
15 30

output:

0

result:

ok found '0.00000', expected '-0.00000', error '-0.00000'

Test #30:

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

input:

3 20
-3 30
6 14
11 40

output:

10.791333850157908131

result:

ok found '10.79133', expected '10.79133', error '0.00000'

Test #31:

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

input:

3 20
-3 30
6 14
11 15

output:

23.220705911859413708

result:

ok found '23.22071', expected '23.22071', error '0.00000'

Test #32:

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

input:

3 20
0 30
-30 0
30 0

output:

628.31853071795859872

result:

ok found '628.31853', expected '628.31853', error '0.00000'

Test #33:

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

input:

3 20
30 20
-30 0
30 0

output:

364.71934867013129866

result:

ok found '364.71935', expected '364.71935', error '0.00000'

Test #34:

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

input:

3 20
-30 20
-30 0
30 0

output:

364.71934867013124248

result:

ok found '364.71935', expected '364.71935', error '0.00000'

Test #35:

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

input:

3 20
30 20
-30 0
30 10

output:

169.45865748006140772

result:

ok found '169.45866', expected '169.45866', error '0.00000'

Test #36:

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

input:

3 1000
0 999
1 1500
0 1500

output:

0.00099800399069616766599

result:

ok found '0.00100', expected '0.00100', error '0.00000'