QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308182#7783. Military ManeuvermshcherbaAC ✓1332ms4348kbC++204.7kb2024-01-19 18:18:422024-01-19 18:18:43

Judging History

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

  • [2024-01-19 18:18:43]
  • 评测
  • 测评结果:AC
  • 用时:1332ms
  • 内存:4348kb
  • [2024-01-19 18:18:42]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const db PI = acos(-1.0);
const db EPS = 1e-9;

struct Pt
{
	db x, y;
	Pt operator+(const Pt& p) const
	{
		return {x + p.x, y + p.y};
	}
	Pt operator-(const Pt& p) const
	{
		return {x - p.x, y - p.y};
	}
	Pt operator*(db d) const
	{
		return {x * d, y * d};
	}
	Pt operator/(db d) const
	{
		return {x / d, y / d};
	}
};

db sq(const Pt& p)
{
	return p.x * p.x + p.y * p.y;
}

db abs(const Pt& p)
{
	return sqrt(sq(p));
}

int sgn(db x)
{
	return (EPS < x) - (x < -EPS);
}

Pt perp(const Pt& p)
{
	return {-p.y, p.x};
}

db dot(const Pt& p, const Pt& q)
{
	return p.x * q.x + p.y * q.y;
}

db cross(const Pt& p, const Pt& q)
{
	return p.x * q.y - p.y * q.x;
}

bool half(const Pt& p)
{
	assert(sgn(p.x) != 0 || sgn(p.y) != 0);
	return sgn(p.y) == -1 || (sgn(p.y) == 0 && sgn(p.x) == -1);
}

ostream& operator<<(ostream& os, const Pt& p)
{
	return os << "(" << p.x << "," << p.y << ")";
}

struct Line
{
	Pt n;
	db c;
	Line (const Pt& _n, db _c): n(_n), c(_c) {}
	db side(const Pt& p) const
	{
		return dot(n, p) + c;
	}
};

bool parallel(const Line& l1, const Line& l2)
{
	return sgn(cross(l1.n, l2.n)) == 0;
}

Pt inter(const Line& l1, const Line& l2)
{
	db d = cross(l1.n, l2.n);
	assert(sgn(d) != 0);
	return perp(l2.n * l1.c - l1.n * l2.c) / d;
}

vector<Pt> hplaneInter(vector<Line> lines)
{
	sort(ALL(lines), []
		(const Line& l1, const Line& l2)
	{
		bool h1 = half(l1.n), h2 = half(l2.n);
		if (h1 != h2)
			return h1 < h2;
		int p = sgn(cross(l1.n, l2.n));
		if (p != 0)
			return p > 0;
		return sgn(l1.c / abs(l1.n) - l2.c / abs(l2.n)) < 0;
	});
	lines.erase(unique(ALL(lines), parallel), lines.end());
	deque<pair<Line, Pt>> d;
	for (const Line& l : lines)
	{
		while (SZ(d) > 1 && sgn(l.side((d.end() - 1)->S)) < 0)
			d.pop_back();
		while (SZ(d) > 1 && sgn(l.side((d.begin() + 1)->S)) < 0)
			d.pop_front();
		if (!d.empty() && sgn(cross(d.back().F.n, l.n)) <= 0)
			return {};
		if (SZ(d) < 2 || sgn(d.front().F.side(inter(l, d.back().F))) >= 0)
		{
			Pt p;
			if (!d.empty())
			{
				p = inter(l, d.back().F);
				if (!parallel(l, d.front().F))
					d.front().S = inter(l, d.front().F);
			}
			d.PB({l, p});
		}
	}
	vector<Pt> res;
	for (auto [l, p] : d)
	{
		if (res.empty()
			|| sgn(sq(p - res.back())) > 0)
			res.PB(p);
	}
	return res;
}

db f(const vector<Pt>& v, db x0)
{
	int n = SZ(v), iMin = 0, iMax = 0;
	FOR(i, 0, SZ(v))
	{
		if (sgn(v[i].x - v[iMin].x) < 0)
			iMin = i;
		if (sgn(v[i].x - v[iMax].x) > 0)
			iMax = i;
	}
	vector pwx(3, vector<db>(n));
	FOR(i, 0, n)
	{
		pwx[0][i] = v[i].x * v[i].x;
		pwx[1][i] = pwx[0][i] * v[i].x;
		pwx[2][i] = pwx[1][i] * v[i].x;
	}
	db s0 = 0, s1 = 0, s2 = 0;
	for (int s : {-1, 1})
	{
		for (int i = iMin; i != iMax;)
		{
			int j = i - s;
			if (j < 0)
				j += n;
			if (j >= n)
				j -= n;
			db dx = v[j].x - v[i].x;
			if (sgn(dx) != 0)
			{
				db k = (v[j].y - v[i].y) / dx;
				db b = cross(v[j], v[i]) / dx;
				db dx2 = (pwx[0][j] - pwx[0][i]) / 2;
				db dx3 = (pwx[1][j] - pwx[1][i]) / 3;
				db dx4 = (pwx[2][j] - pwx[2][i]) / 4;
				s0 += s * (k * dx2 + b * dx);
				s1 += s * (k * dx3 + b * dx2);
				s2 += s * (k * dx4 + b * dx3);
			}
			i = j;
		}
	}
	return s2 - 2 * x0 * s1 + x0 * x0 * s0;
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	db xl, yl, xr, yr;
	int n;
	cin >> xl >> yl >> xr >> yr >> n;
	vector<Pt> v(n);
	for (Pt& p : v)
		cin >> p.x >> p.y;
	vector<Line> boundingLines =
		{{{0, 1}, -yl}, {{-1, 0}, xr},
			{{0, -1}, yr}, {{1, 0}, -xl}};
	vector<Line> linesOuter, linesInner;
	db ans = 0;
	FOR(i, 0, n)
	{
		linesOuter = boundingLines;
		linesInner = boundingLines;
		FOR(j, 0, n)
		{
			if (j == i)
				continue;
			Pt normal = v[j] - v[i];
			db c = -dot(normal, (v[i] + v[j]) / 2);
			linesOuter.PB({normal, c});
			linesInner.PB({normal * (-1), -c});
		}
		vector<Pt> vOuter = hplaneInter(linesOuter);
		vector<Pt> vInner = hplaneInter(linesInner);
		int s = 1;
		for (auto polygon : {vOuter, vInner})
		{
			ans += s * f(polygon, v[i].x);
			for (Pt& p : polygon)
				swap(p.x, p.y);
			reverse(ALL(polygon));
			ans += s * f(polygon, v[i].y);
			s *= -1;
		}
	}
	cout << PI * ans / ((xr - xl) * (yr - yl)) << "\n";
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

0 0 2 2
2
3 1
1 3

output:

8.377580409572785

result:

ok found '8.3775804', expected '8.3775804', error '0.0000000'

Test #2:

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

input:

0 0 2 2
2
5 1
1 3

output:

37.699111843077503

result:

ok found '37.6991118', expected '37.6991118', error '0.0000000'

Test #3:

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

input:

-2911 2151 336 5941
2000
-83 79
-94 47
48 -29
-47 64
84 75
-44 -86
-58 -11
-31 58
20 53
80 -19
-82 74
-60 -26
8 -68
-42 -61
-14 12
-58 -18
92 10
35 -26
71 64
76 89
-80 6
70 4
-96 -99
95 -80
-3 -22
71 -89
-75 17
-35 -82
-59 95
60 48
-74 50
-82 90
-26 5
-75 -31
-45 85
85 14
-70 -57
59 46
55 13
-23 60
...

output:

6657168.142853373661637

result:

ok found '6657168.1428534', expected '6657168.1428534', error '0.0000000'

Test #4:

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

input:

-3013 5287 7654 9132
2000
-19 49
-17 -35
64 68
48 -49
-72 -14
29 -93
-13 -8
-80 11
39 88
-31 82
68 -66
5 41
-74 -8
0 15
11 34
69 -12
15 -86
5 -78
-48 73
10 9
-2 8
81 52
41 -43
-45 -41
-23 60
-40 -45
-26 27
-32 73
8 -20
2 91
46 17
51 -66
-65 -32
37 -9
58 63
-14 -31
60 -56
-85 -22
9 -66
-7 -53
-21 40
...

output:

10130702.494014993309975

result:

ok found '10130702.4940150', expected '10130702.4940150', error '0.0000000'

Test #5:

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

input:

-5561 9559 6905 9930
2000
79 338
2 214
325 -193
-390 -157
-517 943
-759 970
449 901
-369 636
-661 -211
847 -558
223 -564
185 822
-656 -854
-991 -617
-422 -169
-63 -799
327 -911
-960 945
-948 831
-494 93
266 -299
139 -535
796 707
75 -146
10 566
72 -713
-132 -341
348 924
-739 -838
982 995
-445 500
-71...

output:

158891446.623877644538879

result:

ok found '158891446.6238776', expected '158891446.6238778', error '0.0000000'

Test #6:

score: 0
Accepted
time: 1042ms
memory: 4036kb

input:

-5245 -7558 1275 934
2000
-40 125
79 -30
49 13
-127 153
-151 -28
-82 -140
147 131
123 -105
-84 71
-49 -146
-140 82
57 172
-140 -32
-173 24
-55 -101
44 142
-68 -114
122 69
-137 66
19 199
31 109
-161 -66
63 -101
65 -114
166 -66
83 -162
60 70
-19 -134
15 161
-130 22
-130 50
8 -121
150 89
132 44
-131 -3...

output:

11172638.265623591840267

result:

ok found '11172638.2656236', expected '11172638.2656236', error '0.0000000'

Test #7:

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

input:

-7167 6117 -3297 6866
2000
-346 -144
-227 169
-168 -373
-63 -227
-24 405
-232 -163
295 22
222 351
293 41
-335 260
-43 -426
-205 193
163 -284
-406 284
-202 -114
-339 -86
-413 17
-237 -394
-333 -145
-104 416
-478 -53
451 102
85 58
-124 -472
424 -88
394 243
-459 45
12 -490
-9 465
-159 -202
315 -272
-24...

output:

52361392.515027292072773

result:

ok found '52361392.5150273', expected '52361392.5150275', error '0.0000000'

Test #8:

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

input:

-6462 -5871 5937 5853
2000
386 236
-108 937
-722 354
-710 -475
462 613
-884 446
595 -675
168 394
-744 -551
761 -399
-688 258
-53 104
-614 -177
-273 -678
794 -15
224 -911
-146 -216
53 633
2 -664
202 -440
24 437
495 623
-297 682
-520 -48
598 720
-7 353
163 744
557 13
395 588
-157 -672
631 -705
-68 818...

output:

57605018.870116457343102

result:

ok found '57605018.8701165', expected '57605018.8701164', error '0.0000000'

Test #9:

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

input:

792 4703 2923 5458
2000
7281 5289
-5154 2943
-8483 3113
9380 -576
-2191 -291
-8200 898
-192 4724
1161 441
34 3999
8544 3576
-5481 4273
-9792 9565
4854 1262
4254 -3376
-5778 9480
8631 -2225
7129 2187
5344 7740
2975 6174
-2919 -7172
7990 -5117
-6823 -7233
5020 5269
-9874 1051
8841 4586
-3612 -7483
644...

output:

1133083681.545469999313354

result:

ok found '1133083681.5454700', expected '1133083681.5454702', error '0.0000000'

Test #10:

score: 0
Accepted
time: 1013ms
memory: 3972kb

input:

-4075 7303 -1671 8073
2000
-10 305
-1105 -119
-238 205
-1206 -482
943 -89
-1578 223
-520 1158
21 1622
-621 -886
-163 -515
283 1802
36 -1410
213 -1921
-1539 -231
835 148
56 1448
-407 1653
1896 -533
1321 -437
530 172
132 18
1260 586
-363 -220
989 1353
281 -1907
-1116 -801
695 592
1221 -983
1731 -939
-...

output:

205950762.734161972999573

result:

ok found '205950762.7341620', expected '205950762.7341621', error '0.0000000'

Test #11:

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

input:

2121 3865 3457 7582
2000
3902 -1511
-1817 504
-3515 3188
-4470 211
536 1795
2230 -1512
3979 297
2430 901
2368 2525
-2553 -252
476 2279
-3859 2565
-754 396
3358 2726
4787 -664
173 1056
-1154 -1556
-2442 -406
-1838 976
3785 1136
-131 -421
77 4058
3773 2965
1333 -622
4188 -2571
-624 -2051
-1965 4268
-1...

output:

399702074.054006576538086

result:

ok found '399702074.0540066', expected '399702074.0540065', error '0.0000000'

Test #12:

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

input:

5377 -2525 9878 7241
2000
316 9854
1690 3184
-9795 -898
-7924 3181
-2410 1478
-3849 -8880
8447 -487
3826 -2478
1445 -2923
5459 677
8830 -3598
1045 -5139
7231 -6856
-4410 4982
-3180 -2528
-7891 -4137
6686 -3732
-6102 -1926
6562 5714
4562 -5710
223 -9921
2609 -3935
8187 55
-5017 -4465
-1387 -2695
6015...

output:

1061816977.667655587196350

result:

ok found '1061816977.6676556', expected '1061816977.6676595', error '0.0000000'

Test #13:

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

input:

-3243 -8661 4122 -2937
2000
1 7637
0 1870
1 7982
-1 -391
0 -4347
-1 2035
0 -2623
0 6943
0 1511
0 -8789
-1 7213
1 -4998
1 -8958
1 -182
-1 -318
1 3712
0 -3215
1 -5210
1 6983
-1 -2567
1 -470
-1 7652
0 -2394
1 7196
1 280
1 5785
1 545
1 8779
1 1
1 -9675
1 5137
-1 -1160
1 -3955
0 3176
0 -6143
0 519
1 5678...

output:

791760973.958500266075134

result:

ok found '791760973.9585003', expected '791760973.9585004', error '0.0000000'

Test #14:

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

input:

-4763 3483 5561 3747
2000
-3915 1
8391 -1
-4112 0
5453 -1
-8775 1
-2182 0
-3819 1
-2702 1
-7119 1
1279 0
7959 -1
-4345 0
-1024 1
-4853 -1
-2637 1
-2136 -1
-9603 -1
-5869 1
-1765 1
-3625 1
9255 0
4677 1
4660 -1
3250 1
-8156 -1
-2988 0
8492 1
-961 0
9331 -1
-1913 1
-3152 0
8877 -1
8390 0
3420 0
-7929 ...

output:

505360943.970376491546631

result:

ok found '505360943.9703765', expected '505360943.9703766', error '0.0000000'

Test #15:

score: 0
Accepted
time: 1034ms
memory: 4080kb

input:

-8627 -2766 -1956 4443
2000
-4 -9231
-6 -3132
4 176
1 8378
1 6264
-3 -9699
-10 -6369
-9 -4283
-7 7401
1 -1418
7 -5096
7 -7114
-4 -3937
2 5922
-1 6133
6 -8932
-6 3552
2 4767
9 7643
3 4129
4 2295
-5 8379
1 768
-10 -8915
5 4022
-6 -6665
4 4425
-3 6046
6 3827
-5 3831
-6 -6224
5 9807
9 11
5 4503
-6 -5911...

output:

448946370.792788088321686

result:

ok found '448946370.7927881', expected '448946370.7927880', error '0.0000000'

Test #16:

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

input:

-4229 -9182 1776 -5186
2000
8444 3
3252 6
-7072 5
5793 -1
1339 2
-3500 6
-9676 -4
-1101 -8
-4997 7
462 -6
1476 7
-1331 9
561 -4
-951 -6
-466 -8
-8455 2
8033 -5
2982 9
-7803 6
8473 1
674 5
-7228 -1
-1891 -10
-3408 -7
-917 -8
9486 -5
355 9
1212 -4
3712 10
9106 1
9958 1
7446 -5
8816 -1
-1752 4
4285 0
-...

output:

438654068.218460679054260

result:

ok found '438654068.2184607', expected '438654068.2184606', error '0.0000000'

Test #17:

score: 0
Accepted
time: 1024ms
memory: 4080kb

input:

-6880 -3012 949 2588
2000
56 -2490
59 -8874
-90 7871
-48 9340
-29 -4546
72 1776
-22 -8437
-7 5228
6 -2206
89 -5714
71 -6149
44 8645
-17 -8800
19 -8446
-31 -1438
58 4422
-10 -6275
98 -7180
21 -3721
14 3061
-60 -2084
45 4628
-57 -7683
-19 -5389
97 4046
58 5141
-44 288
49 -3579
-39 -7224
94 5901
-68 -3...

output:

411858700.043299257755280

result:

ok found '411858700.0432993', expected '411858700.0432993', error '0.0000000'

Test #18:

score: 0
Accepted
time: 1013ms
memory: 4192kb

input:

2772 -6314 4903 4834
2000
-9330 45
1739 56
1062 -58
6549 -25
2178 88
-6106 -87
-6078 -75
-9429 58
2648 -27
-9516 52
9061 -9
-1775 -3
-6885 74
-4346 27
-1758 -95
-9196 87
-752 -98
1724 -24
825 8
-2431 18
-360 14
1472 52
8871 -71
7205 -39
-8033 -28
8724 8
-5197 -52
9320 -2
2849 -64
-968 -77
9867 100
3...

output:

605362233.752956032752991

result:

ok found '605362233.7529560', expected '605362233.7529563', error '0.0000000'

Test #19:

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

input:

-10000 -10000 10000 10000
2000
8592 4096
9271 1216
8596 5077
9077 1756
9059 3053
8744 4685
8509 4543
7828 4581
8975 2478
9394 2850
9194 3045
9532 1437
9290 1261
8175 4923
8485 4507
8166 4987
8578 4973
9548 2129
9018 3543
8136 5431
8830 2783
9636 2605
8589 2865
9617 1981
9427 1091
7817 5017
9129 1790...

output:

238108908.617580085992813

result:

ok found '238108908.6175801', expected '238108908.6175798', error '0.0000000'

Test #20:

score: 0
Accepted
time: 1036ms
memory: 4020kb

input:

-10000 -10000 10000 10000
2000
6262 7501
9152 454
8076 5537
5939 7930
9638 2163
8615 4078
9554 1084
4352 8207
9578 1188
9456 406
8908 3352
5449 7414
8782 3668
8621 4472
9319 957
6598 6780
8818 2341
6747 7300
9941 555
7653 6219
9183 342
7768 5183
8604 4366
3084 8703
7005 6054
7108 6347
9604 498
9180 ...

output:

397620990.084140896797180

result:

ok found '397620990.0841409', expected '397620990.0841421', error '0.0000000'

Test #21:

score: 0
Accepted
time: 1033ms
memory: 4060kb

input:

-10000 -10000 10000 10000
2000
1066 9157
9386 1781
6605 7086
2309 8912
9690 2029
7780 6101
-590 9528
9389 1295
7597 5489
9036 4111
6848 6367
5728 7783
8672 4455
7349 5754
9546 1194
391 9337
7748 5828
4912 8500
3010 8983
9877 1235
6371 6950
8942 4055
2111 9469
703 9760
7671 5156
7290 5623
-135 9974
8...

output:

554491808.939416766166687

result:

ok found '554491808.9394168', expected '554491808.9394159', error '0.0000000'

Test #22:

score: 0
Accepted
time: 1037ms
memory: 4064kb

input:

-10000 -10000 10000 10000
2000
9179 3249
-7440 6141
1589 9872
-7325 6455
5681 8184
-5197 8181
-4609 8595
8619 4125
6442 6792
-3591 8889
9340 1215
4556 8497
8772 4168
-7033 6910
-6024 7886
9454 1423
2080 9352
799 9732
-1392 9561
-1456 9358
9027 2880
8692 3510
7747 6163
-4921 8380
9405 1846
9325 1029
...

output:

689400531.778384685516357

result:

ok found '689400531.7783847', expected '689400531.7783850', error '0.0000000'

Test #23:

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

input:

-10000 -10000 10000 10000
2000
-413 9522
8730 4470
3507 9168
5383 8069
8670 4427
-9308 3173
7997 5312
4959 8042
9698 943
7838 5266
-1664 9690
-8665 4435
-7997 5929
-8004 5304
6458 7586
1075 9349
-9665 1477
-9045 3807
-2560 9625
-9175 3732
-2041 9416
4209 8993
-4289 8826
-9394 2481
9442 2659
9358 241...

output:

801988277.644851565361023

result:

ok found '801988277.6448516', expected '801988277.6448485', error '0.0000000'

Test #24:

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

input:

-10000 -10000 10000 10000
2000
-8928 -3936
-6761 7287
-9682 -71
-8639 -3984
-9595 2735
293 9693
2163 9632
-8395 5266
69 9738
-7522 6527
-9270 -2254
1248 9688
-9575 -961
9627 1763
-9052 3587
-7114 6320
1541 9699
9483 1490
9715 929
9537 2145
9232 2774
-8662 4803
-2298 9383
-3408 8923
7113 6554
3071 91...

output:

876785969.038407802581787

result:

ok found '876785969.0384078', expected '876785969.0384066', error '0.0000000'

Test #25:

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

input:

-10000 -10000 10000 10000
2000
-9635 -653
-8720 -4280
-5995 7913
-9350 -2497
-5442 8109
-8247 -5020
-9214 3473
-9607 719
-9089 -3142
-9469 -1962
-9849 -106
9096 3352
-4680 -8597
9250 3140
9456 1742
-3524 8952
6527 7385
-1748 9791
-7220 -6715
9498 2723
4248 8776
-2148 9563
-8946 3525
-8594 -4460
-310...

output:

917958796.417641639709473

result:

ok found '917958796.4176416', expected '917958796.4176416', error '0.0000000'

Test #26:

score: 0
Accepted
time: 1041ms
memory: 3972kb

input:

-10000 -10000 10000 10000
2000
-8424 4882
9874 1054
-7516 6283
5824 7919
-9492 2869
-8465 -5065
-7677 6023
9658 1194
-9032 -4038
-1597 9671
-6382 -7575
-7148 6793
-4487 8777
-4574 -8576
5921 7980
-7095 6804
9757 1960
-446 9756
9784 1908
2863 -9539
-860 9863
-9683 1374
-7696 6223
-8488 5254
-9338 262...

output:

949084958.818659782409668

result:

ok found '949084958.8186598', expected '949084958.8186604', error '0.0000000'

Test #27:

score: 0
Accepted
time: 1042ms
memory: 4088kb

input:

-10000 -10000 10000 10000
2000
4185 -8886
7933 -5859
-9624 1869
5116 8492
7405 6679
-5390 8255
3698 -9149
-3048 -9443
-4420 8767
4593 8716
-186 9893
-654 9837
6586 7495
4835 8649
-6838 7288
-9548 2300
9526 2926
2929 9402
3564 9256
5371 8359
-9883 306
-9009 -4168
-6262 -7699
-7990 -5794
8096 5562
391...

output:

962273357.465333223342896

result:

ok found '962273357.4653332', expected '962273357.4653347', error '0.0000000'

Test #28:

score: 0
Accepted
time: 1041ms
memory: 3972kb

input:

-10000 -10000 10000 10000
2000
-9661 -2487
-3295 -9339
6986 -7122
1152 9901
-7469 6523
-8947 4408
9954 641
-9417 -3097
-4042 9040
3350 9383
1721 -9757
5006 8565
-3414 9369
7563 6502
3795 -9153
7684 6358
2612 -9594
-2043 -9715
9761 -1880
-5955 -8019
-181 9958
8931 4398
-9859 -1329
-5689 8176
-7462 65...

output:

962638552.463509917259216

result:

ok found '962638552.4635099', expected '962638552.4635112', error '0.0000000'

Test #29:

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

input:

-10000 -10000 10000 10000
2000
8501 5255
-8375 5447
-35 -9991
1854 9816
9333 3581
8958 -4423
-6372 -7702
-293 9993
-1478 -9890
-8828 4676
1480 9885
-9766 -2134
-8209 5701
-8515 5226
-9521 -3051
-9975 -587
-6593 7507
2775 9596
-6945 7186
-368 9993
-4697 -8821
-9977 633
-8 9993
-7503 -6601
7996 5999
-...

output:

961606219.675291061401367

result:

ok found '961606219.6752911', expected '961606219.6752908', error '0.0000000'

Test #30:

score: 0
Accepted
time: 1060ms
memory: 4060kb

input:

-10000 -10000 10000 10000
2000
-4177 9085
709 -9974
-9702 2419
-9989 -450
-670 -9977
-8072 5901
-7972 -6036
8638 -5038
-9624 -2714
-9108 4127
6539 -7565
5370 -8435
8466 -5320
-6576 -7533
9035 4285
-5956 -8032
9068 -4215
4025 -9154
5545 8321
7320 -6812
-2950 -9554
8695 4939
9065 4221
3229 9464
-9897 ...

output:

961547221.208271503448486

result:

ok found '961547221.2082715', expected '961547221.2082705', error '0.0000000'

Test #31:

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

input:

-10000 -10000 10000 10000
256
5008 -4851
-4668 -5179
-2736 6413
5139 -4712
-2803 6384
1723 6756
-1659 -6772
6259 3072
-5832 -3821
4028 -5691
-6651 -2092
-5179 -4668
6899 1008
-5691 4028
-2317 -6576
-5179 4668
6952 531
6948 581
6789 1588
5691 -4028
-1723 6756
-1659 6772
-2136 -6637
-6576 2317
4596 52...

output:

670393490.381953954696655

result:

ok found '670393490.3819540', expected '670393490.3819546', error '0.0000000'

Test #32:

score: 0
Accepted
time: 18ms
memory: 3880kb

input:

-10000 -10000 10000 10000
288
-456 -8767
6240 6175
-2600 -8385
-4796 -7353
-8740 825
-8511 -2152
575 8760
5716 -6663
-6625 -5760
-5148 -7111
-8200 3135
-6864 5473
8200 -3135
-3300 8135
8000 3615
5057 7176
-8697 1196
-4231 7692
3615 8000
-2951 -8268
2017 -8544
8200 3135
-6663 -5716
-6240 -6175
2241 8...

output:

844114805.061468601226807

result:

ok found '844114805.0614686', expected '844114805.0614687', error '0.0000000'

Test #33:

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

input:

-10000 -10000 10000 10000
256
-2750 9655
-6074 7993
6970 7225
6922 -7271
-9847 -1954
6358 -7769
8030 6025
-9970 1175
-8030 6025
9050 4345
2686 -9673
6439 -7702
-9095 4250
5591 8338
9970 1175
1175 9970
5783 -8206
2750 9655
-4726 -8857
9638 -2809
-7702 -6439
9977 1114
-5095 -8650
3863 -9266
5042 -8681...

output:

965086521.740518212318420

result:

ok found '965086521.7405182', expected '965086521.7405190', error '0.0000000'

Test #34:

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

input:

-10000 -10000 10000 10000
72
-9765 -7270
9547 7554
7270 -9765
-9083 -8106
9083 8106
9547 -7554
8070 -9115
-7050 9925
-8427 8786
7050 -9925
-7050 -9925
8427 -8786
-9030 8165
-8427 -8786
-9450 7675
8165 9030
9450 7675
-7554 9547
-9925 -7050
7675 9450
-7270 9765
-9115 -8070
9450 -7675
8485 -8730
9115 -...

output:

1128792509.417557001113892

result:

ok found '1128792509.4175570', expected '1128792509.4175582', error '0.0000000'

Test #35:

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

input:

-10000 -10000 10000 10000
32
-9272 9271
9272 9271
9272 -9271
9599 8932
-9712 8809
-8809 -9712
8932 -9599
-8932 9599
8809 9712
9271 9272
8831 -9692
-9692 -8831
8809 -9712
-9271 9272
-9271 -9272
9271 -9272
-9712 -8809
-8831 -9692
-9599 8932
8831 9692
-9599 -8932
-8932 -9599
-8831 9692
9692 -8831
-8809...

output:

1182673090.419687509536743

result:

ok found '1182673090.4196875', expected '1182673090.4196880', error '0.0000000'

Test #36:

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

input:

-10000 -10000 10000 10000
80
235 2730
-1221 5278
-1925 7550
-325 3550
8886 -2123
-1355 5610
-1595 6290
1894 917
-2170 9685
2446 453
-550 3925
-1158 5131
885 1930
-1829 7122
-2165 9530
2325 550
3925 -550
5610 -1355
8965 -2130
-1502 6011
3995 -590
-2026 8107
75 2950
-1190 5205
-1410 5755
917 1894
9530...

output:

657040895.887312412261963

result:

ok found '657040895.8873124', expected '657040895.8873124', error '0.0000000'

Test #37:

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

input:

-10000 -10000 10000 10000
96
-5571 9222
6051 -5082
-1885 -90
4835 -4710
1373 -2986
1802 -3261
5715 -4990
2157 -3474
554 -2403
1085 -2790
2765 -3810
-3474 2157
9222 -5571
3293 -4074
9885 -5590
-1789 -202
-4867 5306
-4515 4310
9059 -5562
-4710 4835
-90 -1885
-5166 6387
-5581 9458
7502 -5389
-835 -1210...

output:

836413049.376924753189087

result:

ok found '836413049.3769248', expected '836413049.3769248', error '0.0000000'

Test #38:

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

input:

-10000 -10000 10000 10000
96
6815 -9370
-9201 5918
705 -7290
-9502 7761
-9042 5231
321 -7078
-3265 -4470
-6154 -1153
-7078 321
2510 -8145
2390 -8095
-6879 -22
-4870 -2815
-8898 4689
-4735 -2970
-5665 -1830
-4170 -3585
4689 -8898
-177 -6786
-6081 -1258
-9294 6383
-2815 -4870
-3585 -4170
-6198 -1089
9...

output:

1059819845.874054074287415

result:

ok found '1059819845.8740541', expected '1059819845.8740538', error '0.0000000'

Test #39:

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

input:

-10000 -10000 10000 10000
38
-6467 -5256
-9635 -880
-3179 -8172
-2444 -8683
-6992 -4669
-5155 -6560
-1085 -9520
-1316 -9387
-8765 -2320
-9520 -1085
-4163 -7416
-5256 -6467
-3940 -7595
-1781 -9108
-6660 -5045
-7416 -4163
-880 -9635
-7740 -3755
-2988 -8309
-9387 -1316
-5740 -6005
-8309 -2988
-9108 -17...

output:

401223489.833454668521881

result:

ok found '401223489.8334547', expected '401223489.8334547', error '0.0000000'

Test #40:

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

input:

-10000 -10000 10000 10000
16
-8681 -6822
-6822 -8681
-6998 -8521
-7191 -8342
-9794 -5497
-8521 -6998
-5497 -9794
-7558 -7991
-9578 -5769
-9682 -5639
-8999 -6462
-6462 -8999
-8342 -7191
-5639 -9682
-5769 -9578
-7991 -7558

output:

181599089.452469885349274

result:

ok found '181599089.4524699', expected '181599089.4524700', error '0.0000000'

Test #41:

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

input:

-10000 -10000 10000 10000
10
-9880 -6785
-7472 -9279
-7079 -9628
-7225 -9500
-7775 -9000
-9500 -7225
-9628 -7079
-9279 -7472
-6785 -9880
-9000 -7775

output:

130181610.025646716356277

result:

ok found '130181610.0256467', expected '130181610.0256466', error '0.0000000'

Test #42:

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

input:

-10000 -10000 10000 10000
4
-9480 -9015
-9900 -8575
-8575 -9900
-9015 -9480

output:

55539550.124372176826000

result:

ok found '55539550.1243722', expected '55539550.1243723', error '0.0000000'

Test #43:

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

input:

-10000 -10000 10000 10000
4
-10000 -10000
10000 -10000
-10000 10000
10000 10000

output:

1256637061.435917377471924

result:

ok found '1256637061.4359174', expected '1256637061.4359174', error '0.0000000'

Test #44:

score: 0
Accepted
time: 1326ms
memory: 4080kb

input:

-10000 -10000 10000 10000
2000
2044 2044
-8714 -8714
-918 -918
2587 2587
-6059 -6059
5193 5193
-9894 -9894
-4609 -4609
55 55
2687 2687
3106 3106
8183 8183
2735 2735
-2950 -2950
579 579
-1338 -1338
-6756 -6756
42 42
-169 -169
9040 9040
-9228 -9228
-4915 -4915
-3211 -3211
7013 7013
4183 4183
5113 5113...

output:

1151330698.421488046646118

result:

ok found '1151330698.4214880', expected '1151330698.4214876', error '0.0000000'

Test #45:

score: 0
Accepted
time: 1321ms
memory: 4184kb

input:

-10000 -10000 10000 10000
2000
-6538 -6538
5148 5148
9850 9850
7282 7282
-2282 -2282
-5028 -5028
4922 4922
9956 9956
5469 5469
2292 2292
-6534 -6534
7401 7401
4104 4104
8427 8427
-6193 -6193
-9024 -9024
7928 7928
-2241 -2241
8125 8125
-4976 -4976
-3666 -3666
5405 5405
-5271 -5271
-9353 -9353
-8746 -...

output:

1148135739.933349847793579

result:

ok found '1148135739.9333498', expected '1148135739.9333484', error '0.0000000'

Test #46:

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

input:

-10000 -10000 10000 10000
2000
9476 9476
-9869 -9869
8080 8080
8383 8383
9669 9669
-8486 -8486
8674 8674
-9236 -9236
8525 8525
9227 9227
-8259 -8259
-9401 -9401
-9303 -9303
8737 8737
-9672 -9672
-8361 -8361
-8521 -8521
-9700 -9700
-9360 -9360
-9854 -9854
-8582 -8582
-9997 -9997
8518 8518
-9861 -9861...

output:

980285475.080930233001709

result:

ok found '980285475.0809302', expected '980285475.0809305', error '0.0000000'

Test #47:

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

input:

-10000 -10000 10000 10000
2000
-1646 -1646
742 742
1462 1462
657 657
-1336 -1336
622 622
-1498 -1498
-1007 -1007
1219 1219
260 260
1951 1951
-1476 -1476
713 713
878 878
403 403
1542 1542
1878 1878
-1959 -1959
244 244
384 384
-1830 -1830
-1536 -1536
1554 1554
1423 1423
-1744 -1744
-1731 -1731
1117 11...

output:

170735086.164258837699890

result:

ok found '170735086.1642588', expected '170735086.1642589', error '0.0000000'

Test #48:

score: 0
Accepted
time: 1331ms
memory: 3928kb

input:

-10000 -10000 10000 10000
2000
-4431 -4431
-790 -790
-7329 -7329
6810 6810
-489 -489
-6874 -6874
2089 2089
4399 4399
4905 4905
4808 4808
-4367 -4367
-675 -675
6348 6348
4880 4880
-4601 -4601
5023 5023
-4750 -4750
2922 2922
-3394 -3394
-4671 -4671
3330 3330
-6127 -6127
-6296 -6296
-6393 -6393
-5535 -...

output:

840638278.508628368377686

result:

ok found '840638278.5086284', expected '840638278.5086277', error '0.0000000'

Test #49:

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

input:

-10000 -10000 10000 10000
2000
-10000 10000
10000 -10000
498 498
-644 -644
-1202 -1202
617 617
524 524
1312 1312
1070 1070
-816 -816
756 756
-1934 -1934
1228 1228
-1336 -1336
-1066 -1066
705 705
-1446 -1446
1113 1113
-1038 -1038
-638 -638
1730 1730
282 282
1876 1876
-1613 -1613
158 158
162 162
1195 ...

output:

1156500882.991462469100952

result:

ok found '1156500882.9914625', expected '1156500882.9914625', error '0.0000000'

Test #50:

score: 0
Accepted
time: 1325ms
memory: 4348kb

input:

-10000 -10000 10000 10000
2000
-10000 10000
10000 -10000
2590 2590
2306 2306
3693 3693
1106 1106
483 483
936 936
34 34
820 820
3274 3274
-2947 -2947
-2526 -2526
-2646 -2646
2223 2223
1411 1411
-2181 -2181
-1664 -1664
-1221 -1221
-2188 -2188
1581 1581
-3881 -3881
2733 2733
1613 1613
973 973
3437 3437...

output:

1185552635.415787696838379

result:

ok found '1185552635.4157877', expected '1185552635.4157882', error '0.0000000'

Test #51:

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

input:

-10000 -10000 10000 10000
2000
0 0
-8050 -5931
-6443 7646
-4197 -9076
-6478 -7617
-4838 -8751
552 -9984
-7429 6693
-1481 9889
-5775 -8163
203 -9997
9728 2314
-2339 -9722
-9615 2745
3530 9355
9951 987
3465 -9380
3565 9342
2032 9791
4728 8811
3982 -9172
-9375 -3478
71 9999
-9420 -3354
9588 -2838
9458 ...

output:

982102595.494370222091675

result:

ok found '982102595.4943702', expected '982102595.4943708', error '0.0000000'

Test #52:

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

input:

9999 9999 10000 10000
2
-10000 10000
10000 -10000

output:

41887.899551150389016

result:

ok found '41887.8995512', expected '41887.9020479', error '0.0000001'

Extra Test:

score: 0
Extra Test Passed