QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#191959#6118. Eartheartucup-team1209#AC ✓270ms25212kbC++202.6kb2023-09-30 12:58:532023-09-30 12:58:53

Judging History

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

  • [2023-09-30 12:58:53]
  • 评测
  • 测评结果:AC
  • 用时:270ms
  • 内存:25212kb
  • [2023-09-30 12:58:53]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 500005;
using ll = long long;
using u64 = unsigned long long;
using db = long double;
const db eps = 1e-10;
struct vec2 {
	db x, y;
	db abs() const { return sqrt(x * x + y * y); }
};
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
db operator % (vec2 x, vec2 y) { return x.x * y.x + x.y * y.y; }
db operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
struct seg { vec2 x, y; };
db dist(seg o, vec2 x) {
	if((o.x - o.y) % (x - o.y) <= eps) return (x - o.y).abs();
	if((o.y - o.x) % (x - o.x) <= eps) return (x - o.x).abs();
	return fabs((o.x - x) * (o.y - x) / (o.x - o.y).abs());
}
int n;


db R;

int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> R;
	std::vector<vec2> a(n);
	std::vector<seg> b(n);
	for(int i = 0;i < n;++i) {
		cin >> a[i].x >> a[i].y;
	}
	for(int i = 0;i < n;++i) {
		b[i] = {a[i], a[(i + 1) % n]};
	}
	std::vector<std::pair<db, db>> ok, del;
	std::vector<db> o;
	for(auto [x, y] : b) {
		if(x.y > y.y) std::swap(x, y);
		if(x.y <= 0 && y.y > 0) {
			o.push_back((x.x * (0 - y.y) + y.x * (x.y - 0)) / (x.y - y.y));
		}
	}
	assert(o.size() % 2 == 0);
	sort(o.begin(), o.end());
	for(int i = 0;i < (int) o.size();i += 2) {
		ok.emplace_back(o[i], o[i + 1]);
	}
	for(auto [x, y] : b) {
		if(x.y > y.y) std::swap(x, y);
		if(x.y >= R) continue;
		if(y.y <= -R) continue;
		vec2 mid = {0, 0};
		if(x.y <= 0 && y.y > 0) {
			mid.x = (x.x * (0 - y.y) + y.x * (x.y - 0)) / (x.y - y.y);
		} else {
			mid.x = fabs(y.y) < fabs(x.y) ? y.x : x.x;
		}
		db le = mid.x, ri = mid.x, s = 1e7;
		auto chk = [&](db d) {
			return dist({x, y}, vec2{d, 0}) <= R + eps;
		};
		assert(chk(mid.x));
		for(int i = 0;i < 100;++i) {
			s /= 2;
			if(chk(le - s)) le -= s;
			if(chk(ri + s)) ri += s;
		}
		del.emplace_back(le, ri);
		o.push_back(le);
		o.push_back(ri);
	}
	sort(o.begin(), o.end());
	std::vector<int> cnt(o.size());
	for(auto [l, r] : ok) {
		int L = lower_bound(o.begin(), o.end(), l) - o.begin();
		int R = lower_bound(o.begin(), o.end(), r) - o.begin();
		cnt[L] += 1;
		cnt[R] -= 1;
	}

	for(auto [l, r] : del) {
		int L = lower_bound(o.begin(), o.end(), l) - o.begin();
		int R = lower_bound(o.begin(), o.end(), r) - o.begin();
		cnt[L] -= 1;
		cnt[R] += 1;
	}
	db ans = 0;
	for(int i = 0;i + 1 < (int) o.size();++i) {
		if(i) cnt[i] += cnt[i - 1];
		if(cnt[i] > 0) {
			ans += o[i + 1] - o[i];
		}
	}
	printf("%.10Lf\n", ans);
}

详细

Test #1:

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

input:

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

output:

0.0000000000

result:

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

Test #2:

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

input:

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

output:

9.9999999998

result:

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

Test #3:

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

input:

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

output:

190.1569471563

result:

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

Test #4:

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

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

result:

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

Test #5:

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

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

result:

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

Test #6:

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

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

result:

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

Test #7:

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

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

result:

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

Test #8:

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

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

result:

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

Test #9:

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

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

result:

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

Test #10:

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

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

result:

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

Test #11:

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

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

result:

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

Test #12:

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

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

result:

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

Test #13:

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

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

result:

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

Test #14:

score: 0
Accepted
time: 29ms
memory: 5304kb

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

result:

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

Test #15:

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

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

result:

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

Test #16:

score: 0
Accepted
time: 26ms
memory: 4952kb

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

result:

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

Test #17:

score: 0
Accepted
time: 10ms
memory: 4800kb

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

result:

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

Test #18:

score: 0
Accepted
time: 10ms
memory: 4824kb

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

result:

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

Test #19:

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

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

result:

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

Test #20:

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

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

result:

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

Test #21:

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

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

result:

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

Test #22:

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

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

result:

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

Test #23:

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

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

result:

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

Test #24:

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

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

result:

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

Test #25:

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

input:

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

output:

0.0000000000

result:

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

Test #26:

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

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

result:

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

Test #27:

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

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

result:

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

Test #28:

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

input:

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

output:

0.0000000000

result:

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

Test #29:

score: 0
Accepted
time: 74ms
memory: 7724kb

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

result:

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

Test #30:

score: 0
Accepted
time: 266ms
memory: 19524kb

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

result:

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

Test #31:

score: 0
Accepted
time: 43ms
memory: 6560kb

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

result:

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

Test #32:

score: 0
Accepted
time: 39ms
memory: 5744kb

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

result:

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

Test #33:

score: 0
Accepted
time: 181ms
memory: 17600kb

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

result:

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

Test #34:

score: 0
Accepted
time: 154ms
memory: 15320kb

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

result:

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

Test #35:

score: 0
Accepted
time: 67ms
memory: 7504kb

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

result:

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

Test #36:

score: 0
Accepted
time: 144ms
memory: 19616kb

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

result:

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

Test #37:

score: 0
Accepted
time: 77ms
memory: 7792kb

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

result:

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

Test #38:

score: 0
Accepted
time: 226ms
memory: 18392kb

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

result:

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

Test #39:

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

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

result:

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

Test #40:

score: 0
Accepted
time: 94ms
memory: 14080kb

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:

697371.3638420968

result:

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

Test #41:

score: 0
Accepted
time: 37ms
memory: 6192kb

input:

18340 57
1000000 346830
999023 346830
999023 14
999007 14
999007 346830
998820 346830
998820 3
998313 3
998313 346830
997489 346830
997489 12
997360 12
997360 346830
995764 346830
995764 21
995562 21
995562 346830
995260 346830
995260 28
994866 28
994866 346830
994608 346830
994608 56
993822 56
9938...

output:

332728.3325475408

result:

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

Test #42:

score: 0
Accepted
time: 164ms
memory: 18252kb

input:

87372 39
1000000 200793
999952 200793
999952 14
999906 14
999906 200793
999884 200793
999884 -12
999883 -12
999883 200793
999859 200793
999859 17
999848 17
999848 200793
999809 200793
999809 -24
999795 -24
999795 200793
999762 200793
999762 18
999759 18
999759 200793
999699 200793
999699 36
999698 3...

output:

182507.8667805986

result:

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

Test #43:

score: 0
Accepted
time: 53ms
memory: 9384kb

input:

46716 57
1000000 705268
999898 705268
999898 -40
999772 -40
999772 705268
999362 705268
999362 27
998971 27
998971 705268
998792 705268
998792 25
998650 25
998650 705268
998631 705268
998631 16
998384 16
998384 705268
998379 705268
998379 -53
997769 -53
997769 705268
997502 705268
997502 1
997492 1
...

output:

568090.2510506917

result:

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

Test #44:

score: 0
Accepted
time: 44ms
memory: 7428kb

input:

23652 69
1000000 871420
998038 871420
998038 36
996765 36
996765 871420
996651 871420
996651 39
996546 39
996546 871420
995740 871420
995740 61
995479 61
995479 871420
995360 871420
995360 32
995239 32
995239 871420
995227 871420
995227 26
995222 26
995222 871420
994586 871420
994586 24
994354 24
99...

output:

284513.7245671835

result:

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

Test #45:

score: 0
Accepted
time: 132ms
memory: 14412kb

input:

73788 70
1000000 684240
999655 684240
999655 40
999605 40
999605 684240
999574 684240
999574 54
999503 54
999503 684240
999485 684240
999485 46
999466 46
999466 684240
999453 684240
999453 50
999434 50
999434 684240
999366 684240
999366 52
999295 52
999295 684240
999237 684240
999237 58
999187 58
99...

output:

87818.2843892636

result:

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

Test #46:

score: 0
Accepted
time: 90ms
memory: 10668kb

input:

43980 79
1000000 513263
999623 513263
999623 1
999583 1
999583 513263
999535 513263
999535 63
999533 63
999533 513263
998365 513263
998365 68
998106 68
998106 513263
997779 513263
997779 -26
997727 -26
997727 513263
997682 513263
997682 15
997552 15
997552 513263
997546 513263
997546 -6
997449 -6
99...

output:

152516.4367141443

result:

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

Test #47:

score: 0
Accepted
time: 75ms
memory: 9112kb

input:

38372 61
1000000 974881
999667 974881
999667 58
999343 58
999343 974881
999312 974881
999312 8
999288 8
999288 974881
999091 974881
999091 -29
999076 -29
999076 974881
999054 974881
999054 46
999014 46
999014 974881
998255 974881
998255 17
998132 17
998132 974881
998066 974881
998066 48
997973 48
99...

output:

252559.0656197456

result:

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

Test #48:

score: 0
Accepted
time: 113ms
memory: 12552kb

input:

61596 26
1000000 605003
999688 605003
999688 18
999607 18
999607 605003
999596 605003
999596 -2
999588 -2
999588 605003
999375 605003
999375 -1
999214 -1
999214 605003
998858 605003
998858 14
998809 14
998809 605003
998590 605003
998590 -4
998557 -4
998557 605003
998172 605003
998172 -4
998054 -4
99...

output:

326248.4764114771

result:

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

Test #49:

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

input:

706 553084
-1000000 146399
-999926 140164
-999983 133722
-999908 110930
-999934 105260
-999999 105200
-999952 95962
-999942 72469
-999950 72089
-999938 54367
-999925 51331
-999906 36316
-999928 31760
-999993 30263
-999904 20816
-999948 7597
-999910 6526
-999949 6092
-999952 -6864
-999977 -39129
-999...

output:

104987.5962824939

result:

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

Test #50:

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

input:

448 929649
-999999 -915718
-995302 -929610
-975675 -929690
-933078 -929672
-926181 -929675
-923555 -929670
-914897 -929659
-893093 -929659
-842850 -929626
-806908 -929669
-800237 -929699
-791320 -929685
-781307 -929629
-724467 -929632
-716252 -929625
-711614 -929619
-666412 -929615
-665911 -929642
-...

output:

23435.6126998403

result:

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

Test #51:

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

input:

622 75451
-1000000 29393
-999999 19749
-999989 17732
-999941 11259
-999952 4756
-999907 4480
-999994 2786
-999922 -402
-999945 -4754
-999962 -5627
-999984 -10400
-999905 -10463
-999994 -16724
-999967 -20371
-999924 -24608
-999916 -41902
-999963 -42219
-999957 -69285
-999978 -72408
-999934 -74569
-99...

output:

376537.4649921357

result:

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

Test #52:

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

input:

899 754715
-1000000 17037
-999904 2543
-999994 -2423
-999958 -6464
-999917 -9416
-999969 -11970
-999992 -30146
-999966 -40560
-999998 -46965
-999998 -53911
-999917 -54853
-999949 -63825
-999963 -69333
-999935 -69672
-999903 -73875
-999936 -85717
-999919 -94916
-999996 -111536
-999912 -127465
-999964...

output:

46173.3814975025

result:

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

Test #53:

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

input:

870 139405
-1000000 103686
-999911 99940
-999946 88715
-999994 85911
-999957 84523
-999980 81935
-999932 81408
-999992 78898
-999916 61842
-999950 61662
-999979 56264
-999937 46054
-999957 45491
-999957 31319
-999903 23401
-999929 22229
-999978 21867
-999907 20397
-999926 9634
-999904 8281
-999918 2...

output:

250201.4261259772

result:

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

Test #54:

score: 0
Accepted
time: 25ms
memory: 5336kb

input:

10001 533288
-1000000 -505112
-999983 -507116
-999921 -507383
-999955 -508208
-999942 -509194
-999930 -509213
-999945 -509392
-999962 -509955
-999958 -510356
-999981 -512164
-999938 -513418
-999937 -514001
-999913 -514801
-999996 -515569
-999965 -515744
-999932 -515858
-999985 -517458
-999988 -51799...

output:

0.0000000000

result:

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

Test #55:

score: 0
Accepted
time: 22ms
memory: 5088kb

input:

10001 32863
-1000000 9497
-999946 9448
-999974 9088
-999967 9080
-999979 8976
-999914 8935
-999973 8349
-999987 8292
-999951 7891
-999929 7845
-999956 7578
-999916 7327
-999981 7184
-999923 7095
-999972 7080
-999942 6775
-999969 6574
-999999 6351
-999961 6324
-999954 5265
-999944 5014
-999934 4810
-...

output:

5048.7799498238

result:

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

Test #56:

score: 0
Accepted
time: 26ms
memory: 5168kb

input:

10001 670187
-1000000 -602542
-999990 -602944
-999949 -603301
-999992 -606053
-999902 -606102
-999931 -606890
-999923 -607185
-999956 -608707
-999905 -608825
-999940 -608995
-999966 -612452
-999970 -613204
-999953 -613351
-999918 -613752
-999925 -614886
-999905 -615022
-999939 -615165
-999933 -61578...

output:

0.0000000000

result:

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

Test #57:

score: 0
Accepted
time: 25ms
memory: 5232kb

input:

10001 615401
-1000000 -558432
-999938 -558469
-999982 -558771
-999942 -559219
-999955 -559675
-999958 -560278
-999989 -560419
-999921 -561084
-999990 -561231
-999985 -561766
-999957 -562064
-999991 -562374
-999974 -563955
-999974 -564375
-999983 -564847
-999989 -565146
-999908 -566758
-999992 -56766...

output:

0.0000000000

result:

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

Test #58:

score: 0
Accepted
time: 19ms
memory: 5004kb

input:

10000 243265
-1000000 -206787
-999936 -207691
-999965 -207721
-999906 -208147
-999959 -208203
-999906 -208403
-999988 -208691
-999961 -209114
-999952 -209609
-999940 -211921
-999934 -212408
-999952 -212713
-999957 -213352
-999966 -213875
-999999 -214448
-999942 -214523
-999997 -215035
-999965 -21528...

output:

0.0000000000

result:

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

Test #59:

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

input:

4 9277
-9912 -6898
-9471 -9279
5751 -9301
-3912 9306

output:

0.0000000000

result:

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

Test #60:

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

input:

60 1041
-9987 9
-9914 -1019
-9858 -1078
-8990 -1042
-8768 -1030
-7902 -1012
-7349 -1017
-7247 -1035
-7098 -1016
-7051 -1007
-5132 -1090
-3995 -1063
-3212 -1079
-2038 -1064
-2030 -1005
-1750 -1004
-1636 -1085
-1278 -1041
-989 -1056
-880 -1013
1274 -1035
2292 -1079
3196 -1018
4668 -998
4934 -1038
5692...

output:

2644.5210098044

result:

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

Test #61:

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

input:

67 9843
-9998 -3569
-9905 -5210
-9918 -6674
-9949 -8695
-9652 -9847
-9539 -9851
-9502 -9844
-8940 -9818
-7516 -9838
-5941 -9807
-5831 -9836
-4871 -9873
-4692 -9877
-3079 -9855
-527 -9854
132 -9828
209 -9803
3557 -9882
8307 -9852
8458 -9857
9152 -9853
9947 -9769
9975 -7455
9975 45
9997 688
9951 2908
...

output:

0.0000000000

result:

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

Test #62:

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

input:

15 4953
-10000 3489
-9935 2828
-9934 1018
-9943 -4226
-4172 -4994
2551 -4912
4798 -5002
7023 -4947
9989 -4078
9951 -3074
9908 934
9225 4966
7174 4991
6983 4947
-7661 4988

output:

4470.5145651806

result:

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

Test #63:

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

input:

44 5240
-9985 4881
-9919 4550
-9969 3986
-9956 3883
-9973 53
-9928 -1313
-9951 -2552
-9976 -3631
-8436 -5245
-5392 -5249
-1633 -5206
-1352 -5239
-592 -5252
897 -5210
1006 -5269
2138 -5196
3873 -5282
4600 -5261
7205 -5211
7560 -5259
8263 -5213
9021 -5234
9920 -5112
9973 -4131
9985 -941
9980 -783
9960...

output:

1577.9298580196

result:

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

Test #64:

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

input:

4 1
1000000 1000000
-999999 -999994
-1000000 1000000
-999999 -1000000

output:

0.1715789608

result:

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

Test #65:

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

input:

4 1
1000000 1
999998 1
999997 -1000000
1000000 -1000000

output:

0.0000009998

result:

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

Test #66:

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

input:

4 1
99948 1
99947 -99950
99950 -99950
99950 1

output:

0.0000100047

result:

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

Test #67:

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

input:

4 499999
-499998 1000000
500000 1000000
499999 -1000000
-499999 -999950

output:

0.0000123751

result:

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

Test #68:

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

input:

4 499999
-499999 -1000000
499999 -999950
499998 1000000
-500000 1000000

output:

0.0000123751

result:

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

Test #69:

score: 0
Accepted
time: 270ms
memory: 25212kb

input:

100000 50000
-997263 -48631
-997262 1371
-997261 -48630
-997260 1372
-997259 -48629
-997258 1373
-997257 -48628
-997256 1374
-997255 -48627
-997254 1375
-997253 -48626
-997252 1376
-997251 -48625
-997250 1377
-997249 -48624
-997248 1378
-997247 -48623
-997246 1379
-997245 -48622
-997244 1380
-997243...

output:

0.9999500022

result:

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

Test #70:

score: 0
Accepted
time: 133ms
memory: 20680kb

input:

100000 1
-949960 -949959
-949958 949960
949960 949959
949959 -949958
-949948 -949948
-949949 949950
949948 949950
949950 -949948
-949938 -949939
-949940 949940
949939 949939
949940 -949938
-949929 -949928
-949928 949928
949930 949930
949928 -949928
-949920 -949919
-949920 949918
949919 949919
949920...

output:

25713.0003390937

result:

ok found '25713.00034', expected '25713.00035', error '0.00000'

Test #71:

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

input:

4 10
2 -14
14 2
-2 14
-14 -2

output:

0.0000000000

result:

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

Test #72:

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

input:

4 30
-100 0
0 -100
100 0
0 100

output:

115.1471862573

result:

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

Test #73:

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

input:

8 723777
885124 -723777
885124 -514064
514064 885124
514064 723777
-514064 723777
-514064 885124
-885124 -514064
-885124 -723777

output:

0.0000100056

result:

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

Test #74:

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

input:

4 499999
-1000000 -500000
1000000 -499999
1000000 500000
-1000000 499998

output:

500000.7499112833

result:

ok found '500000.74991', expected '500000.75000', error '0.00000'

Test #75:

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

input:

3 10000
300000 300000
600000 600000
400000 500000

output:

0.0000000000

result:

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

Test #76:

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

input:

3 100000
300000 300000
600000 600000
400000 500000

output:

0.0000000000

result:

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

Test #77:

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

input:

28 100
0 -100
300 -100
300 200
1200 200
1200 -100
1500 -100
1500 200
2400 200
2400 -100
2700 -100
2700 200
3600 200
3600 -200
3300 -200
3300 100
3000 100
3000 -200
2100 -200
2100 100
1800 100
1800 -200
900 -200
900 100
600 100
600 -500
3900 -500
3900 500
0 500

output:

699.9999999986

result:

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

Test #78:

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

input:

28 100
0 -100
200 -100
200 200
1200 200
1200 -100
1400 -100
1400 200
2400 200
2400 -100
2600 -100
2600 200
3600 200
3600 -200
3300 -200
3300 100
3100 100
3100 -200
2100 -200
2100 100
1900 100
1900 -200
900 -200
900 100
700 100
700 -500
3800 -500
3800 500
0 500

output:

0.0000000000

result:

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

Test #79:

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

input:

9 1
10 5
5 5
5 -5
-5 -5
-4 0
-5 5
-10 5
-10 -10
10 -10

output:

6.9801960969

result:

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

Test #80:

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

input:

9 1
10 5
5 5
6 0
5 -5
-5 -5
-5 5
-10 5
-10 -10
10 -10

output:

4.9999999996

result:

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

Test #81:

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

input:

16 100
-1000 -1000
-1 -1000
-1 -1
-100 0
100 0
1 -1
1 -1000
1000 -1000
1000 -1
900 0
1000 1
1000 1000
-1000 1000
-1000 1
-900 0
-1000 -1

output:

1199.9999999996

result:

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

Test #82:

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

input:

125 1
-1074 -727
-1000 -788
-944 -804
-863 -802
-807 -770
-727 -696
-677 -696
-627 -726
-542 -793
-474 -812
-413 -811
-333 -774
-230 -704
-205 -695
-155 -695
-43 -737
38 -753
136 -750
205 -699
258 -663
258 -616
106 -616
-37 -560
-232 -421
23 -399
374 -341
625 -252
639 -333
626 -431
480 -570
259 -616...

output:

406.4260065158

result:

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