QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#467673#6118. Eartheartskip2004WA 62ms23804kbC++203.1kb2024-07-08 17:06:432024-07-08 17:06:43

Judging History

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

  • [2024-07-08 17:06:43]
  • 评测
  • 测评结果:WA
  • 用时:62ms
  • 内存:23804kb
  • [2024-07-08 17:06:43]
  • 提交

answer

// test
// https://qoj.ac/submission/467496
#include <bits/stdc++.h>
using namespace std;
typedef long double LD;

const LD eps = 1e-8;
const LD INF = 1e18;
int sgn (LD x) { return x > eps ? 1 : (x < -eps ? -1 : 0); }

#define cp const point &
struct point {
	LD x, y;
	point operator + (cp a) const { return {x + a.x, y + a.y}; }
	point operator - (cp a) const { return {x - a.x, y - a.y}; }
	point operator * (LD a) const { return {x * a, y * a}; }
	point operator / (LD a) const { return {x / a, y / a}; }
	point unit() const {
		LD s = hypot (x, y);
		return {x / s, y / s};
	}
	point rot90() const { return {-y, x}; }
};

LD det (cp a, cp b) { return a.x * b.y - b.x * a.y; }
LD dot (cp a, cp b) { return a.x * b.x + a.y * b.y; }

#define cl const line &
struct line {
	point s, t;
};

point line_inter (cl a, cl b) {
	LD s1 = det (a.t - a.s, b.s - a.s);
	LD s2 = det (a.t - a.s, b.t - a.s);
	return (b.s * s2 - b.t * s1) / (s2 - s1);
}

bool two_side (cp a, cp b, cl c) {
	return (sgn (det (a - c.s, c.t - c.s)) <= 0) + (sgn (det (b - c.s, c.t - c.s)) <= 0) == 1;
}

void work() {

	LD R;
	int n;
	cin >> n >> R;
	R -= 3e-7;

	vector <point> a;
	
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a.push_back({x, y});
	}


	{
		LD area = 0;
		for (int i = 0; i < n; i++) area += det (a[i], a[(i + 1) % n]);
		if (area < 0) {
			reverse(a.begin(), a.end());
		}
	}

	vector < pair <LD, int> > e;

	for (int i = 0; i < n; i++) {
		point u = a[i % n];
		point v = a[(i + 1) % n];
		if (sgn(u.y) <= 0 && sgn(v.y) > 0) {
			e.push_back({line_inter ({u, v}, {{0, 0}, {1, 0}}).x, -1});
		} else if (sgn (u.y) > 0 && sgn (v.y) <= 0) {
			e.push_back({line_inter ({u, v}, {{0, 0}, {1, 0}}).x, 1});
		}
	}

	for (int i = 0; i < n; i++) {
		point u = a[i % n];
		if (abs(u.y) < R) {
			LD dx = sqrt(R * R - u.y * u.y);
			e.push_back({u.x - dx, 2});
			e.push_back({u.x + dx, -2});
		}
		point v = a[(i + 1) % n];
		if (max(u.y, v.y) <= -R) continue;
		if (min(u.y, v.y) >= R) continue;
		point norm = (v - u).rot90().unit();
		point w = v + norm * R;
		point x = u + norm * R;
		if (!sgn(w.y) && !sgn(x.y)) continue;
		vector <line> lines = {
			{u, v},
			{v, w},
			{w, x},
			{x, u}
		};
		vector <LD> inter;
		for (auto l : lines) {
			if (two_side (l.s, l.t, {{0, 0}, {1, 0}})) {
				inter.push_back(line_inter (l, {{0, 0}, {1, 0}}).x);
			}
		}
		sort(inter.begin(), inter.end());
		if (inter.size() && inter.back() - inter.front() > eps) {
			e.push_back({inter.front(), 2});
			e.push_back({inter.back(), -2});
		}
	}

	sort(e.begin(), e.end());
	LD last = -INF, ans = 0;
	int cnt = 0, ban = 0;
	for (auto [x, d] : e) {
		//cerr << "last = " << last << " x = " << x << " " << cnt << " " << ban << endl;
		if (cnt == 1 && !ban) ans += x - last;
		if (abs(d) == 1) {
			cnt += d;
		} else {
			ban += d;
		}
		assert (0 <= cnt && cnt <= 1);
		last = x;
	}
	assert (cnt == 0);
	cout << fixed << setprecision(9) << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int T = 1;
//	cin >> T;
	for (int ca = 1; ca <= T; ca ++) {
		work();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 4056kb

input:

4 5
-5 -5
5 -5
5 5
-5 5

output:

0.000000600

result:

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

Test #2:

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

input:

4 5
-10 -10
10 -10
10 10
-10 10

output:

10.000000600

result:

ok found '10.00000', expected '10.00000', error '0.00000'

Test #3:

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

input:

9 10
-100 -80
-90 130
-30 150
0 160
100 130
120 90
110 -60
80 -100
0 -120

output:

190.156947758

result:

ok found '190.15695', expected '190.15695', error '0.00000'

Test #4:

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

input:

457 414687
-996315 -725321
-986403 -603614
-984900 -99226
-943685 -319681
-985352 -704158
-984699 -905259
-969935 -927143
-465900 -963727
-310171 -992145
-453426 -949729
-643489 -909695
-709791 -884030
-787622 -849046
-526296 -903166
-408863 -906869
-263787 -933392
-473870 -789072
-593393 -759966
-6...

output:

0.000000000

result:

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

Test #5:

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

input:

3157 635592
-998983 -17775
-993005 314040
-992532 -397616
-989247 708857
-985292 589314
-982046 726451
-979965 687632
-985621 240199
-978188 782690
-976339 41585
-981782 -274061
-974948 -410150
-980813 -585511
-980789 -865528
-981492 -862416
-984939 -322700
-984251 -496171
-985237 -472502
-991879 -4...

output:

0.000000000

result:

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

Test #6:

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

input:

1105 296370
-995471 952274
-991091 -838912
-968716 -981056
-955777 -928445
-879545 -975529
-834750 -968694
-825703 -878252
-787229 -998682
-764718 -954650
-732902 -919340
-610938 -966507
-267412 -971184
-68946 -980880
-178705 -973066
-291779 -953553
-347594 -912646
-338352 -904672
-270551 -821414
-1...

output:

0.000000000

result:

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

Test #7:

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

input:

179 22982
-998218 -375932
-924871 -833274
-965464 -861372
-304042 -941903
46407 -942280
576051 -973956
150160 -901679
604511 -911920
778636 -915852
-865584 -871767
-768265 -792995
-593904 -801716
-31277 -868485
479247 -885297
797358 -910090
449130 -870385
370979 -829124
-438450 -784467
-739280 -6550...

output:

497512.615655546

result:

ok found '497512.61566', expected '497512.61565', error '0.00000'

Test #8:

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

input:

3292 364845
-999918 23115
-999238 -495220
-996555 524055
-993572 419978
-990246 -441487
-988731 493394
-987187 271949
-990286 -487104
-991159 -687002
-990332 -768047
-993275 -524304
-995312 -47770
-996316 -77665
-996912 -928704
-990291 -798112
-987083 -940798
-989169 -241346
-987846 -234987
-972976 ...

output:

0.000000000

result:

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

Test #9:

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

input:

431 245611
-999674 -738083
-962850 -478189
-941103 -683461
-950693 -723371
-805609 -881791
-714279 -987279
-734606 -917431
-729365 -889819
-579494 -900362
-550372 -834907
-904231 -720665
-869101 -717255
-824019 -711973
-565569 -769652
-515548 -724811
-361500 -998030
-366800 -967623
-309405 -965964
-...

output:

0.000000000

result:

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

Test #10:

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

input:

4628 771925
-999694 -176559
-999057 559136
-997722 740255
-998118 -532115
-997228 75078
-995395 -886460
-997053 153364
-995648 107732
-995663 368365
-988307 591328
-987914 444405
-990856 376975
-989333 106701
-984376 333516
-986560 116181
-990328 -66424
-981382 191264
-987644 -210220
-991226 -68250
...

output:

0.000000000

result:

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

Test #11:

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

input:

2937 717845
-998210 -682431
-996872 -887362
-984299 -865479
-960730 -958800
-959288 -998581
-915390 -941386
-915084 -941225
-870233 -992911
-759945 -996265
-463081 -993143
185428 -998477
309666 -999404
255022 -976930
229775 -959030
230936 -961109
234734 -972436
218732 -965431
260601 -995989
103112 -...

output:

0.000000000

result:

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

Test #12:

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

input:

4511 974292
-999476 -606738
-999096 -723712
-992306 -944394
-991809 -987714
-988923 -835882
-990546 -197898
-989906 -224486
-988631 -715774
-985857 -696734
-984655 -673361
-983650 -593114
-984945 -565742
-986117 -314889
-983507 12004
-977152 -542680
-962273 -871586
-966937 -809794
-970586 -733453
-9...

output:

0.000000000

result:

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

Test #13:

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

input:

1482 953437
-999701 -531118
-993174 -257827
-980094 -924148
-960541 -858744
-953510 -870425
-947870 -987956
-936077 -885214
-960348 -802355
-976424 -644804
-985648 -558705
-987112 -373731
-973395 -283308
-969368 -107184
-959895 -513223
-949966 -404476
-942421 -481016
-956164 -614383
-947493 -714466
...

output:

0.000000000

result:

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

Test #14:

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

input:

10001 851814
-999848 293276
-999261 -639166
-998728 -369611
-998983 -17775
-993520 -962370
-992983 -876893
-991811 -990246
-997047 -253251
-995527 -431256
-992585 -645211
-991813 -912868
-991091 -838912
-992756 -569264
-987687 -914262
-996368 -205687
-992164 -433526
-992532 -397616
-991879 -431244
-...

output:

0.000000000

result:

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

Test #15:

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

input:

10001 336169
-999896 577082
-999822 184210
-998594 -35591
-997796 258516
-996867 34117
-996756 -391496
-997881 -727378
-998210 -682431
-998056 -958016
-990958 -970394
-986200 -957419
-974805 -973552
-959288 -998581
-960730 -958800
-956901 -936187
-949352 -941331
-944301 -942604
-951341 -963718
-9528...

output:

0.000000000

result:

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

Test #16:

score: 0
Accepted
time: 6ms
memory: 4708kb

input:

10001 788227
-999874 674874
-999099 699732
-999701 -171220
-999812 -224313
-999557 -160461
-998302 -245251
-998701 -635019
-998526 -736484
-998412 -818031
-998073 -96296
-997156 138491
-996595 -926080
-988909 -813093
-985644 -796265
-984394 -844416
-985689 -855227
-981891 -861305
-981316 -891524
-98...

output:

0.000000000

result:

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

Test #17:

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

input:

10001 198360
-999842 932608
-999523 380111
-998834 139995
-998652 -117584
-998755 850942
-998037 845586
-997580 582854
-998349 -148853
-998515 -628231
-998201 -639030
-998116 -840988
-998114 -531248
-998320 -223776
-997232 569927
-997235 168891
-995406 569364
-994666 562210
-994000 34156
-995345 -25...

output:

0.000000000

result:

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

Test #18:

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

input:

10001 327410
-999928 9352
-999585 -676208
-999113 -416060
-998934 -694011
-999013 -484553
-999191 11324
-999485 328101
-999204 546226
-998663 -864092
-999029 823882
-998181 -719693
-997646 -820651
-997029 -525350
-997576 58842
-998212 -291824
-998221 -526066
-998281 -157179
-998232 602133
-996352 -8...

output:

0.000000000

result:

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

Test #19:

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

input:

19 87
-89 23
-31 -55
72 -30
92 9
29 -32
44 33
27 17
23 20
24 1
-46 -7
41 51
80 72
-61 5
-77 22
39 94
-4 71
-22 79
-46 97
-87 61

output:

0.000000000

result:

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

Test #20:

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

input:

13 87
-61 7
-9 -82
-5 -62
-1 -16
27 -39
22 -53
28 -81
87 10
59 -20
68 -3
9 -5
32 87
-47 -6

output:

0.000000000

result:

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

Test #21:

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

input:

13 24
-82 74
-64 -67
-45 -13
-26 2
100 -90
71 -54
74 -21
16 -14
98 -1
92 35
84 66
97 98
14 40

output:

0.000000000

result:

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

Test #22:

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

input:

18 23
-99 -55
-20 -81
-64 -64
69 -40
99 -97
57 -15
-11 -52
0 -22
80 11
62 100
23 96
63 73
18 14
13 77
-34 38
-24 2
-94 54
-83 -21

output:

2.956610391

result:

ok found '2.95661', expected '2.95661', error '0.00000'

Test #23:

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

input:

16 50
-76 37
-72 -77
4 -52
19 -75
37 -44
42 -33
45 -27
64 -27
70 -65
71 -34
68 -23
78 79
8 7
-7 95
-6 39
-72 56

output:

0.000000000

result:

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

Test #24:

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

input:

14 54
-93 -75
-29 -89
-76 -46
-38 -73
-47 -13
-13 -2
17 -65
61 -99
29 -30
85 81
84 81
-5 -7
72 90
-64 -6

output:

0.000000000

result:

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

Test #25:

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

input:

9 44
-82 -23
17 -86
31 -12
66 -29
88 3
19 50
-33 -27
-70 -15
-55 37

output:

0.000000000

result:

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

Test #26:

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

input:

16 73
-79 -81
-22 -93
12 -38
55 -4
94 -63
92 -10
87 98
2 92
41 40
-11 97
15 50
32 2
5 -29
-6 -63
-39 11
-42 58

output:

0.000000000

result:

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

Test #27:

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

input:

20 62
-98 -54
-97 -60
73 -81
70 -39
1 -2
-5 12
-21 23
-31 24
-64 -29
-62 -22
-87 -8
-37 69
56 14
68 10
69 10
94 -81
76 28
28 58
-24 79
-84 41

output:

0.000000000

result:

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

Test #28:

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

input:

9 99
-90 53
-66 -92
8 -93
-56 -37
0 -45
95 -88
-8 -30
41 49
-69 1

output:

0.000000000

result:

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

Test #29:

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

input:

23758 42
999891 36
998928 178
999811 36
998891 178
999794 36
998852 178
999669 36
998717 178
999551 36
998128 178
999516 36
997501 178
999350 36
997181 178
999275 36
997001 178
998599 36
996786 178
998502 36
996660 178
998380 36
995557 178
998196 36
995222 178
997848 36
994381 178
997842 36
993623 1...

output:

181485.756136754

result:

ok found '181485.75614', expected '181485.74982', error '0.00000'

Test #30:

score: 0
Accepted
time: 62ms
memory: 23804kb

input:

89098 100
999972 87
999857 278
999943 87
999701 278
999659 87
999618 278
999651 87
999589 278
999621 87
999450 278
999579 87
999356 278
999553 87
999110 278
999516 87
999049 278
999443 87
998921 278
999386 87
998760 278
999353 87
998661 278
999333 87
998653 278
999307 87
998557 278
999152 87
998537 ...

output:

42.837794014

result:

ok found '42.83779', expected '42.83779', error '0.00000'

Test #31:

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

input:

17198 9
999818 3
999579 401
998839 3
999557 401
998313 3
999189 401
997890 3
998142 401
997541 3
998104 401
997100 3
998052 401
996425 3
998028 401
996340 3
997767 401
996000 3
997489 401
995998 3
996716 401
995447 3
996079 401
995059 3
995539 401
993759 3
994367 401
993753 3
993994 401
993667 3
992...

output:

19947.934505775

result:

ok found '19947.93451', expected '19947.93108', error '0.00000'

Test #32:

score: 0
Accepted
time: 9ms
memory: 5780kb

input:

12538 71
999508 -38
999900 224
999243 -38
997800 224
998518 -38
996913 224
996174 -38
996435 224
996122 -38
995267 224
995886 -38
993656 224
995158 -38
993254 224
993472 -38
991121 224
992934 -38
990973 224
992555 -38
990564 224
992374 -38
989040 224
991361 -38
988792 224
990504 -38
985959 224
98962...

output:

15527.864561140

result:

ok found '15527.86456', expected '15527.86407', error '0.00000'

Test #33:

score: 0
Accepted
time: 34ms
memory: 17292kb

input:

65730 79
999935 18
999936 311
999932 18
999770 311
999898 18
999749 311
999772 18
999643 311
999668 18
999362 311
999490 18
999332 311
998865 18
999310 311
998792 18
998986 311
998676 18
998971 311
998569 18
998863 311
998384 18
998748 311
998198 18
998650 311
997974 18
998631 311
997502 18
998581 3...

output:

741.210380125

result:

ok found '741.21038', expected '741.21037', error '0.00000'

Test #34:

score: 0
Accepted
time: 15ms
memory: 13276kb

input:

52762 24
999966 -12
999655 270
999878 -12
999605 270
999663 -12
999574 270
999643 -12
999485 270
999503 -12
999466 270
999442 -12
999434 270
999266 -12
999366 270
999237 -12
999295 270
999170 -12
999187 270
999110 -12
999165 270
998894 -12
999133 270
998819 -12
998892 270
998544 -12
998867 270
99844...

output:

51298.208612152

result:

ok found '51298.20861', expected '51298.20692', error '0.00000'

Test #35:

score: 0
Accepted
time: 12ms
memory: 8376kb

input:

22030 10
999623 -4
999638 312
999583 -4
999535 312
999533 -4
998106 312
998365 -4
997779 312
997727 -4
997682 312
997552 -4
997449 312
997546 -4
997246 312
996821 -4
994236 312
996487 -4
993684 312
996172 -4
992726 312
995518 -4
992509 312
995195 -4
992346 312
995160 -4
991850 312
994853 -4
991802 3...

output:

761340.793686323

result:

ok found '761340.79369', expected '761340.77233', error '0.00000'

Test #36:

score: 0
Accepted
time: 41ms
memory: 15312kb

input:

87406 33
999996 33
999948 110
999992 33
999782 110
999920 33
999667 110
999919 33
999343 110
999668 33
999327 110
999613 33
999312 110
999607 33
999288 110
999375 33
999229 110
999213 33
999091 110
999033 33
999076 110
998809 33
999054 110
998753 33
999049 110
998698 33
999014 110
998558 33
998846 1...

output:

28667.821538381

result:

ok found '28667.82154', expected '28667.82110', error '0.00000'

Test #37:

score: 0
Accepted
time: 13ms
memory: 6240kb

input:

27382 91
999756 88
999773 105
998972 88
999759 105
998867 88
999730 105
998638 88
999367 105
998591 88
999329 105
998512 88
999318 105
998398 88
998870 105
998334 88
998818 105
997611 88
998434 105
997005 88
998338 105
996684 88
998073 105
996666 88
997242 105
996538 88
997154 105
996383 88
996911 1...

output:

2698.561654009

result:

ok found '2698.56165', expected '2698.56137', error '0.00000'

Test #38:

score: 0
Accepted
time: 48ms
memory: 14260kb

input:

78350 61
999971 21
999982 211
999858 21
999969 211
999751 21
999876 211
999742 21
999632 211
999648 21
999606 211
999613 21
999600 211
999578 21
999596 211
999462 21
999577 211
999384 21
999405 211
999335 21
999356 211
998897 21
999258 211
998879 21
999209 211
998651 21
999152 211
998395 21
999151 2...

output:

2180.247741699

result:

ok found '2180.24774', expected '2180.24768', error '0.00000'

Test #39:

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

input:

19372 42
1000000 779761
998891 779761
998891 13
998852 13
998852 779761
998717 779761
998717 -14
998128 -14
998128 779761
997501 779761
997501 -2
997181 -2
997181 779761
997001 779761
997001 -2
996786 -2
996786 779761
996660 779761
996660 39
995557 39
995557 779761
995222 779761
995222 -10
993623 -1...

output:

398726.544879201

result:

ok found '398726.54488', expected '398726.54294', error '0.00000'

Test #40:

score: -100
Wrong Answer
time: 22ms
memory: 14356kb

input:

78564 8
1000000 829540
999637 829540
999637 7
999618 7
999618 829540
999589 829540
999589 8
999426 8
999426 829540
999049 829540
999049 8
999004 8
999004 829540
998760 829540
998760 8
998661 8
998661 829540
998653 829540
998653 7
998557 7
998557 829540
998480 829540
998480 7
998319 7
998319 829540
9...

output:

737476.111279183

result:

wrong answer 1st numbers differ - expected: '697371.36384', found: '737476.11128', error = '0.05751'