QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#519499#1463. Closest Pair Algorithmcrimson231AC ✓5065ms397928kbC++1710.0kb2024-08-14 20:33:102024-08-14 20:33:10

Judging History

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

  • [2024-08-14 20:33:10]
  • 评测
  • 测评结果:AC
  • 用时:5065ms
  • 内存:397928kb
  • [2024-08-14 20:33:10]
  • 提交

answer

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <cassert>
#include <cstdint>
typedef long long ll;
//typedef long double ld;
typedef double ld;
const ll INF = 1e18;
const int LEN = 250;
const ld TOL = 1e-9;
const ld PI = acos(-1);
inline int sign(const ll& x) { return x < 0 ? -1 : !!x; }
inline int sign(const ld& x) { return x < -TOL ? -1 : x > TOL ? 1 : 0; }
inline bool zero(const ld& x) { return !sign(x); }
inline void norm(ld x) {
	while (sign(x) < 0) x += 2 * PI;
	while (sign(x - 2 * PI) >= 0) x -= 2 * PI;
	return;
}

int N, M, E, OD[LEN], Q[LEN];
ld ANS[LEN][LEN];
struct Pos {
	int x, y;
	Pos(int X = 0, int Y = 0) : x(X), y(Y) {}
	bool operator == (const Pos& p) const { return x == p.x && y == p.y; }
	bool operator != (const Pos& p) const { return x != p.x || y != p.y; }
	bool operator < (const Pos& p) const { return x == p.x ? y < p.y : x < p.x; }
	bool operator <= (const Pos& p) const { return x == p.x ? y <= p.y : x <= p.x; }
	Pos operator + (const Pos& p) const { return { x + p.x, y + p.y }; }
	Pos operator - (const Pos& p) const { return { x - p.x, y - p.y }; }
	Pos operator * (const int& n) const { return { x * n, y * n }; }
	Pos operator / (const int& n) const { return { x / n, y / n }; }
	ll operator * (const Pos& p) const { return (ll)x * p.x + (ll)y * p.y; }
	ll operator / (const Pos& p) const { return (ll)x * p.y - (ll)y * p.x; }
	Pos operator ^ (const Pos& p) const { return { x * p.x, y * p.y }; }
	Pos& operator += (const Pos& p) { x += p.x; y += p.y; return *this; }
	Pos& operator -= (const Pos& p) { x -= p.x; y -= p.y; return *this; }
	Pos& operator *= (const int& scale) { x *= scale; y *= scale; return *this; }
	Pos& operator /= (const int& scale) { x /= scale; y /= scale; return *this; }
	Pos operator - () const { return { -x, -y }; }
	Pos operator ~ () const { return { -y, x }; }
	Pos operator ! () const { return { y, x }; }
	ll xy() const { return (ll)x * y; }
	ll Euc() const { return (ll)x * x + y * y; }
	int Man() const { return std::abs(x) + std::abs(y); }
	ld mag() const { return hypot(x, y); }
	ld rad() const { return atan2(y, x); }
	friend ld rad(const Pos& p1, const Pos& p2) { return atan2l(p1 / p2, p1 * p2); }
	int quad() const { return y > 0 || y == 0 && x >= 0; }
	friend bool cmpq(const Pos& a, const Pos& b) { return (a.quad() != b.quad()) ? a.quad() < b.quad() : a / b > 0; }
	friend std::istream& operator >> (std::istream& is, Pos& p) { is >> p.x >> p.y; return is; }
	friend std::ostream& operator << (std::ostream& os, const Pos& p) { os << p.x << " " << p.y; return os; }
} P[LEN];
const Pos O = { 0, 0 }, INVAL = { -1, -1 };
typedef std::vector<Pos> Polygon;
ll cross(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) / (d3 - d2); }
ll cross(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) / (d4 - d3); }
ll dot(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d2); }
ll dot(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) * (d4 - d3); }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3) { ll ret = cross(d1, d2, d3); return ret < 0 ? -1 : !!ret; }
int ccw(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { ll ret = cross(d1, d2, d3, d4); return ret < 0 ? -1 : !!ret; }
ld projection(const Pos& d1, const Pos& d2, const Pos& d3) { return (d2 - d1) * (d3 - d1) / (d2 - d1).mag(); }
ld projection(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return (d2 - d1) * (d4 - d3) / (d2 - d1).mag(); }
bool on_seg_strong(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && dot(d1, d3, d2) >= 0; }
bool on_seg_weak(const Pos& d1, const Pos& d2, const Pos& d3) { return !ccw(d1, d2, d3) && dot(d1, d3, d2) > 0; }
bool collinear(const Pos& d1, const Pos& d2, const Pos& d3, const Pos& d4) { return !ccw(d1, d2, d3) && !ccw(d1, d2, d4); }
bool intersect(const Pos& s1, const Pos& s2, const Pos& d1, const Pos& d2, const bool f = 1) {
	//f : include end of seg, !f : ignore end of seg
	bool f1 = ccw(s1, s2, d1) * ccw(s2, s1, d2) > 0;
	bool f2 = ccw(d1, d2, s1) * ccw(d2, d1, s2) > 0;
	if (!f) return f1 && f2;
	bool f3 = on_seg_strong(s1, s2, d1) ||
		on_seg_strong(s1, s2, d2) ||
		on_seg_strong(d1, d2, s1) ||
		on_seg_strong(d1, d2, s2);
	return (f1 && f2) || f3;
}
struct Seg {
	short int u, v;//idx
	Seg(short int u = 0, short int v = 0) : u(u), v(v) {}
	Pos s() const { return P[v] - P[u]; }
	Pos p() const { return Pos(u, v); }
	int ccw(const Pos& p0) const { return sign(cross(P[u], P[v], p0)); }
	bool operator < (const Seg& S) const {
		assert(O != s()); assert(O != S.s());
		bool f1 = O < s();
		bool f2 = O < S.s();
		if (f1 != f2) return f1;
		ll CCW = s() / S.s();
		return !CCW ? S.ccw(P[u]) > 0 : CCW < 0;
		//return !CCW ? !S.ccw(P[u]) ? p() < S.p() : S.ccw(P[u]) > 0 : CCW < 0;
	}
	bool operator == (const Seg& S) const { return s() / S.s() == 0 && s() * S.s() > 0; }
} events[LEN * LEN];
struct Slope {
	Seg seg;
	ld ans;
	Slope(Seg se = Seg(0, 0), ld a = 0) : seg(se), ans(a) {}
};
typedef std::vector<Slope> vslope;
typedef std::vector<Seg> vseg;
typedef std::vector<ld> vld;
vslope slopes[LEN][LEN];
vseg segs[LEN][LEN];
vld angs[LEN][LEN];
ld dist(const Pos& p, const Pos& q) { return (p - q).mag(); }
ld sweep(const int& i, const int& j) {
	Pos I, J;
	I = P[i], J = P[j];
	auto theta = [&](const Pos& vec) -> ld {
		Pos K = -~(J - I);
		return rad(K, vec);
		};

	ld total = 0;
	const vseg& SS = segs[i][j];
	const vld& AA = angs[i][j];
	const int sz = SS.size();
	for (int k = 0; k < sz; k++) {
		const Seg& S0 = SS[k], & S1 = SS[(k + 1) % sz];
		const ld& A0 = AA[k], & A1 = AA[(k + 1) % sz];
		if (sign(A0) <= 0) continue;
		ld len = (J - I).mag();
		ld hi = std::min(theta(S0.s()), (ld)(PI * .5));
		ld lo = std::max(theta(S1.s()), -(ld)(PI * .5));
		if (sign(A0 - len) >= 0) {
			total += hi - lo;
			continue;
		}
		ld ratio = std::max(-(ld)1., std::min((ld)1., (ld)(A0 / len)));
		ld phi = acos(ratio);
		if (sign(hi - phi) > 0) {
			if (sign(lo - phi) > 0) total += hi - lo;
			else total += hi - phi;
		}
		if (sign(lo + phi) < 0) {
			if (sign(hi + phi) < 0) total += -(lo - hi);
			else total += -(lo + phi);
		}
	}
	return total;
}
void solve() {
	std::cin.tie(0)->sync_with_stdio(0);
	std::cout.tie(0);
	std::cout << std::fixed;
	std::cout.precision(10);
	memset(P, 0, sizeof P);
	memset(Q, 0, sizeof Q);
	memset(OD, 0, sizeof OD);
	std::cin >> N;
	if (N == 2) { std::cout << "1.0000000000\n"; return; }

	for (int i = 0; i < N; i++) std::cin >> P[i];
	std::sort(P, P + N);
	for (int i = 0; i < N; i++) OD[i] = i, Q[i] = i;

	E = 0;
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			events[E++] = Seg(i, j);
			events[E++] = Seg(j, i);
		}
	}
	std::sort(events, events + E);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			ANS[i][j] = -INF;
	
	ld ans = INF;
	for (int i = 0; i < N; i++) {
		for (int j = i - 1; j >= 0; j--) {
			ANS[i][j] = ans;
			ans = std::min(ans, dist(P[i], P[j]));
		}
	}
	
	for (int i = 0; i < E; i++) {
		int u = events[i].u, v = events[i].v;
		int ou = OD[u], ov = OD[v];
		OD[u] = ov; OD[v] = ou;
		Q[ou] = v; Q[ov] = u;

		assert(ov - ou == 1);

		ans = ou <= 1 ? INF : ANS[Q[ou - 1]][Q[0]];
		if (ou >= 2) ans = std::min(ans, dist(P[Q[0]], P[Q[ou - 1]]));
		for (int j = ou - 1; j >= 0; j--) {
			ANS[v][Q[j]] = ans;
			//slopes[v][Q[j]].push_back(Slope(Seg(u, v), ans));
			segs[v][Q[j]].push_back(Seg(u, v));
			angs[v][Q[j]].push_back(ans);
			ans = std::min(ans, dist(P[v], P[Q[j]]));
		}
		for (int j = ov - 1; j >= 0; j--) {
			ANS[u][Q[j]] = ans;
			//slopes[u][Q[j]].push_back(Slope(Seg(u, v), ans));
			segs[u][Q[j]].push_back(Seg(u, v));
			angs[u][Q[j]].push_back(ans);
			ans = std::min(ans, dist(P[u], P[Q[j]]));
		}

		if (ov < N - 1) {
			ANS[Q[ov + 1]][u] = ans;
			//slopes[Q[ov + 1]][u].push_back(Slope(Seg(u, v), ans));
			segs[Q[ov + 1]][u].push_back(Seg(u, v));
			angs[Q[ov + 1]][u].push_back(ans);
			ans = std::min(ans, dist(P[u], P[Q[ov + 1]]));
			ANS[Q[ov + 1]][v] = ans;
			//slopes[Q[ov + 1]][v].push_back(Slope(Seg(u, v), ans));
			segs[Q[ov + 1]][v].push_back(Seg(u, v));
			angs[Q[ov + 1]][v].push_back(ans);
			ans = std::min(ans, dist(P[v], P[Q[ov + 1]]));
			ans = std::min(ans, ANS[Q[ov + 1]][Q[0]]);
		}
		for (int j = ov + 2; j < N; j++) {
			ans = std::min(ans, ANS[Q[j]][Q[0]]);
			ANS[Q[j]][u] = ans;
			//slopes[Q[j]][u].push_back(Slope(Seg(u, v), ans));
			segs[Q[j]][u].push_back(Seg(u, v));
			angs[Q[j]][u].push_back(ans);
			ans = std::min(ans, dist(P[u], P[Q[j]]));
			ANS[Q[j]][v] = ans;
			//slopes[Q[j]][v].push_back(Slope(Seg(u, v), ans));
			segs[Q[j]][v].push_back(Seg(u, v));
			angs[Q[j]][v].push_back(ans);
			ans = std::min(ans, dist(P[v], P[Q[j]]));
		}

		//slopes[v][u].push_back(Slope(Seg(u, v), -INF));
		segs[v][u].push_back(Seg(u, v));
		angs[v][u].push_back(-INF);
	}

	ld total = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (i == j) continue;
			total += sweep(i, j);
		}
	}

	std::cout << total / (2 * PI) << "\n";
	//std::cout << "Size of Pos: " << sizeof(Pos) << " bytes\n";
	//std::cout << "Size of Seg: " << sizeof(Seg) << " bytes\n";
	//std::cout << "Size of Slope: " << sizeof(Slope) << " bytes\n";

	return;
}
int main() { solve(); return 0; }//boj18497
//Petrozavodsk Programming Camp > Winter 2020 > Day 8: Almost Algoritmic Contest J

/*

3
-1000000 0
1000000 0
1000000 1
1.5000004

5
4 -10
-3 0
-8 6
-9 4
-5 0
3.4242720071

5
-395 310
597 -448
-290 300
-352 -283
-499 -368
2.8473923420

30
-938 702
950 -131
-649 190
431 793
29 606
-887 -555
742 265
-972 419
-28 -399
-316 727
-654 160
-74 694
168 438
-997 604
-430 -836
809 -790
-581 516
677 -721
947 976
-559 -140
-692 -902
-828 927
-562 711
258 -715
761 243
143 -106
803 -109
-760 430
-264 -146
270 905

21.4411311891

*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
0 0
0 1
1 0
1 1

output:

5.0000000000

result:

ok found '5.0000000', expected '5.0000000', error '0.0000000'

Test #2:

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

input:

3
0 0
0 1
1 0

output:

2.5000000000

result:

ok found '2.5000000', expected '2.5000000', error '0.0000000'

Test #3:

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

input:

2
3 4
5 6

output:

1.0000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #4:

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

input:

3
-1000000 0
1000000 0
1000000 1

output:

1.5000003979

result:

ok found '1.5000004', expected '1.5000004', error '0.0000000'

Test #5:

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

input:

5
4 -10
-3 0
-8 6
-9 4
-5 0

output:

3.4242720071

result:

ok found '3.4242720', expected '3.4242720', error '0.0000000'

Test #6:

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

input:

5
-395 310
597 -448
-290 300
-352 -283
-499 -368

output:

2.8473923420

result:

ok found '2.8473923', expected '2.8473923', error '0.0000000'

Test #7:

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

input:

10
-6 -1
10 -6
-7 -8
2 -5
-9 -5
-2 1
3 -2
9 -10
-1 5
1 -1

output:

11.5335911149

result:

ok found '11.5335911', expected '11.5335911', error '0.0000000'

Test #8:

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

input:

10
-563 -366
-256 502
904 625
773 -242
470 920
-873 -152
369 339
109 110
714 762
107 -69

output:

9.7395960245

result:

ok found '9.7395960', expected '9.7395960', error '0.0000000'

Test #9:

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

input:

30
4 10
10 -6
-7 -9
3 2
5 -3
-2 -1
9 -10
2 -7
6 9
-5 5
5 10
-3 -4
-3 0
-2 9
0 7
2 8
10 -4
3 5
4 -6
7 -1
-8 2
-8 -3
6 4
-9 0
-1 -8
-7 1
7 4
-1 -7
9 -9
1 -8

output:

39.8173317024

result:

ok found '39.8173317', expected '39.8173317', error '0.0000000'

Test #10:

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

input:

30
-938 702
950 -131
-649 190
431 793
29 606
-887 -555
742 265
-972 419
-28 -399
-316 727
-654 160
-74 694
168 438
-997 604
-430 -836
809 -790
-581 516
677 -721
947 976
-559 -140
-692 -902
-828 927
-562 711
258 -715
761 243
143 -106
803 -109
-760 430
-264 -146
270 905

output:

21.4411311891

result:

ok found '21.4411312', expected '21.4411312', error '0.0000000'

Test #11:

score: 0
Accepted
time: 64ms
memory: 14576kb

input:

60
-57 70
-55 -35
-76 21
-30 56
-19 75
66 96
3 -57
-94 4
64 30
48 -38
43 6
92 15
-47 -78
-85 -24
84 -18
-27 28
-81 70
93 8
-79 -100
-45 55
85 20
-79 -98
-46 -86
-65 45
-35 -39
-92 -29
38 -11
97 59
-29 22
-18 72
-73 26
-81 -49
-99 3
89 72
-3 -99
-13 17
-60 -81
21 -71
-14 34
-31 -73
-16 -75
-48 42
54 ...

output:

50.7164955703

result:

ok found '50.7164956', expected '50.7164956', error '0.0000000'

Test #12:

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

input:

60
-1770 -5520
-5544 3148
-1744 4969
7804 -9016
6952 9818
447 -8049
-6123 -6377
7183 -6928
-9778 2246
2132 3608
-9801 3893
3 4803
9027 -6153
-8625 725
5761 9073
-2283 -4292
-6925 -2400
9303 8826
-3585 -6206
-346 5393
8416 -6776
-9629 -4611
1656 8044
-7135 -9368
2235 -1434
9832 -5980
4977 -6167
887 -...

output:

62.8398163588

result:

ok found '62.8398164', expected '62.8398164', error '0.0000000'

Test #13:

score: 0
Accepted
time: 51ms
memory: 14788kb

input:

60
-163498 -30302
-345724 646083
-612360 -740665
678763 305271
-773339 301150
-519423 553953
-87625 -832281
-164733 476742
62019 199517
916534 -968558
-504532 787190
830366 -364158
-432172 840849
-702154 722780
-881679 -826972
969462 -387613
34095 -130739
736702 -916629
465648 485860
-596725 797379
...

output:

64.1098302827

result:

ok found '64.1098303', expected '64.1098303', error '0.0000000'

Test #14:

score: 0
Accepted
time: 291ms
memory: 40276kb

input:

100
55 100
45 95
-71 33
70 -100
-17 85
-76 78
-83 -1
-87 67
-31 -76
17 96
-18 66
-80 -41
-58 -10
56 72
4 19
-56 75
-77 -79
33 -86
9 -30
54 5
-31 94
84 50
-45 75
45 -69
70 -5
-40 12
98 31
99 -31
46 -49
-98 -85
73 51
61 -10
-82 25
-37 -78
-1 44
2 -75
98 -61
61 -29
-83 -7
53 -19
-58 33
88 -9
88 6
95 50...

output:

102.5036853191

result:

ok found '102.5036853', expected '102.5036853', error '0.0000000'

Test #15:

score: 0
Accepted
time: 285ms
memory: 40340kb

input:

100
-2145 -3976
6481 1795
2773 6858
968 1068
3020 410
6842 5269
-4046 5388
-8540 -7364
-8675 -8325
7475 -7112
-5952 -8190
-8780 52
5610 -6970
6140 3806
-3880 -1842
-6763 -5660
1347 6636
4900 4245
-7529 4879
391 4629
3006 -1823
-8983 8300
-7285 -643
-9430 7059
-737 -8747
1865 -7802
-1523 7841
6239 -1...

output:

93.3476354560

result:

ok found '93.3476355', expected '93.3476355', error '0.0000000'

Test #16:

score: 0
Accepted
time: 284ms
memory: 40688kb

input:

100
-921745 691002
-962015 -160749
-480023 -34066
-343131 -110768
-231448 -403357
106013 34960
896030 -598173
-127337 544913
-381132 505651
138159 311881
-646788 31263
-120639 242108
-565258 738932
865191 -116949
295077 -87673
-73628 -517530
850182 -677471
994023 -826688
-567069 436849
921215 336313...

output:

102.0997096650

result:

ok found '102.0997097', expected '102.0997097', error '0.0000000'

Test #17:

score: 0
Accepted
time: 2465ms
memory: 258532kb

input:

200
-9443 -8106
4368 4606
8058 7890
453 -776
-7768 -289
-1757 -8854
-8404 3535
-2576 -4678
-6462 -7679
-8980 -9693
-1243 -8214
4956 6575
-3882 -7199
-1326 -7967
-5234 3605
-4341 -382
-3869 4314
-4835 -550
2136 -3197
2496 -2888
-9330 2380
3664 -7934
-9549 -3014
2763 -7755
6846 -9655
-8124 -2063
-2566...

output:

338.6896033383

result:

ok found '338.6896033', expected '338.6896033', error '0.0000000'

Test #18:

score: 0
Accepted
time: 2432ms
memory: 258132kb

input:

200
525065 434645
-624702 -527174
-717713 -766539
-473771 -936088
14914 -141548
-751249 239135
1827 191797
-419595 678678
412154 899832
-575551 541949
-621213 643205
-466563 -166466
-950664 172983
37645 -80742
797573 144438
175462 -121873
-176478 -714701
-645119 -677982
222077 -363093
-551052 148715...

output:

145.0097772360

result:

ok found '145.0097772', expected '145.0097772', error '0.0000000'

Test #19:

score: 0
Accepted
time: 4900ms
memory: 397412kb

input:

250
3693 9045
3805 1961
9287 5288
-6529 -3751
3611 -4955
1110 -9510
8178 9660
2481 9133
4711 -822
5794 -4424
-3374 4932
9638 9647
4293 -3952
-1703 3065
-6545 1336
738 9677
-243 -1729
-5946 -5708
-9996 -8622
-6586 -2082
2480 4
3105 8519
420 6380
-7349 -2302
-1872 -4054
1959 -4783
4400 -3676
-4878 -30...

output:

388.9436034338

result:

ok found '388.9436034', expected '388.9436034', error '0.0000000'

Test #20:

score: 0
Accepted
time: 4846ms
memory: 397640kb

input:

250
961822 144657
-919115 -298876
-971841 -850551
-8328 -120425
758135 361158
-229246 541609
-54684 -528701
455377 -783260
-332531 -202924
-416393 -990497
296199 801812
989528 -515050
800556 719975
860428 596049
546360 -398451
-548518 -239670
784117 -351745
-307726 965794
334556 -597209
741562 75871...

output:

281.5271026368

result:

ok found '281.5271026', expected '281.5271026', error '0.0000000'

Test #21:

score: 0
Accepted
time: 4871ms
memory: 397780kb

input:

250
-480491 -551298
-637223 -268146
-424322 622688
-905391 -762438
617172 -750062
792146 -4478
-710266 594597
624584 -417880
675962 850019
-756658 795092
-287109 -317341
436746 427896
-398057 542221
811077 372972
-362428 -587087
373566 -129535
181207 -92687
402754 -393048
-30175 440303
-431914 -6862...

output:

328.2431164456

result:

ok found '328.2431164', expected '328.2431164', error '0.0000000'

Test #22:

score: 0
Accepted
time: 4896ms
memory: 397596kb

input:

250
-127758 964590
-6321 614577
313086 -538290
-797660 883572
65902 -35917
-480017 -278594
-58648 -47263
775414 582136
577208 67385
655359 284066
274882 123490
141242 600130
137995 -447095
618209 -931278
302525 -367615
980295 -3794
-300900 -615275
-990439 -339280
-748145 264029
-610534 330905
987064...

output:

288.9256005056

result:

ok found '288.9256005', expected '288.9256005', error '0.0000000'

Test #23:

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

input:

10
-500 9
-482 8
-437 7
-366 6
-279 5
-170 4
-41 3
117 2
294 1
500 0

output:

8.4778678450

result:

ok found '8.4778678', expected '8.4778678', error '0.0000000'

Test #24:

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

input:

10
-1000000 9
-955362 8
-866715 7
-733524 6
-555815 5
-333297 4
-66243 3
245223 2
600624 1
999998 0

output:

8.7902444520

result:

ok found '8.7902445', expected '8.7902445', error '0.0000000'

Test #25:

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

input:

30
-2000 29
-1993 28
-1975 27
-1944 26
-1903 25
-1851 24
-1792 23
-1727 22
-1652 21
-1568 20
-1476 19
-1376 18
-1264 17
-1142 16
-1009 15
-863 14
-711 13
-555 12
-390 11
-216 10
-32 9
165 8
368 7
577 6
794 5
1018 4
1250 3
1489 2
1738 1
1997 0

output:

31.9700998833

result:

ok found '31.9700999', expected '31.9700999', error '0.0000000'

Test #26:

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

input:

30
-1000000 29
-995405 28
-986220 27
-972393 26
-953994 25
-930868 24
-903234 23
-870959 22
-834070 21
-792535 20
-746439 19
-695756 18
-640451 17
-580557 16
-516108 15
-446937 14
-373253 13
-295030 12
-212204 11
-124851 10
-32912 9
63624 8
164860 7
270583 6
380738 5
495436 4
614693 3
738593 2
86700...

output:

32.9031901228

result:

ok found '32.9031901', expected '32.9031901', error '0.0000000'

Test #27:

score: 0
Accepted
time: 64ms
memory: 14068kb

input:

60
-5000 59
-4997 58
-4986 57
-4970 56
-4948 55
-4923 54
-4891 53
-4853 52
-4810 51
-4760 50
-4705 49
-4648 48
-4583 47
-4515 46
-4440 45
-4359 44
-4272 43
-4179 42
-4078 41
-3972 40
-3861 39
-3742 38
-3616 37
-3485 36
-3350 35
-3208 34
-3061 33
-2907 32
-2748 31
-2584 30
-2415 29
-2240 28
-2058 27
...

output:

71.8095007562

result:

ok found '71.8095008', expected '71.8095008', error '0.0000000'

Test #28:

score: 0
Accepted
time: 56ms
memory: 13620kb

input:

60
-1000000 59
-998938 58
-996753 57
-993433 56
-989018 55
-983454 54
-976758 53
-968906 52
-959936 51
-949821 50
-938590 49
-926218 48
-912763 47
-898176 46
-882440 45
-865575 44
-847621 43
-828533 42
-808352 41
-786949 40
-764409 39
-740717 38
-715970 37
-690117 36
-663118 35
-634993 34
-605708 33...

output:

75.1855261427

result:

ok found '75.1855261', expected '75.1855261', error '0.0000000'

Test #29:

score: 0
Accepted
time: 294ms
memory: 40016kb

input:

100
-20000 99
-19994 98
-19980 97
-19959 96
-19933 95
-19898 94
-19858 93
-19805 92
-19748 91
-19678 90
-19603 89
-19522 88
-19433 87
-19337 86
-19235 85
-19125 84
-19009 83
-18884 82
-18748 81
-18596 80
-18433 79
-18264 78
-18085 77
-17902 76
-17707 75
-17501 74
-17288 73
-17072 72
-16849 71
-16622...

output:

134.6770261829

result:

ok found '134.6770262', expected '134.6770262', error '0.0000000'

Test #30:

score: 0
Accepted
time: 294ms
memory: 40080kb

input:

100
-1000000 99
-999576 98
-998726 97
-997491 96
-995876 95
-993844 94
-991403 93
-988570 92
-985331 91
-981708 90
-977678 89
-973256 88
-968471 87
-963274 86
-957651 85
-951668 84
-945301 83
-938531 82
-931329 81
-923711 80
-915673 79
-907256 78
-898408 77
-889160 76
-879505 75
-869408 74
-858899 7...

output:

138.9839975883

result:

ok found '138.9839976', expected '138.9839976', error '0.0000000'

Test #31:

score: 0
Accepted
time: 1030ms
memory: 150768kb

input:

150
-40000 149
-39984 148
-39960 147
-39926 146
-39886 145
-39839 144
-39784 143
-39722 142
-39647 141
-39565 140
-39480 139
-39389 138
-39290 137
-39181 136
-39063 135
-38936 134
-38800 133
-38655 132
-38498 131
-38334 130
-38163 129
-37985 128
-37797 127
-37601 126
-37399 125
-37193 124
-36979 123...

output:

228.6693055851

result:

ok found '228.6693056', expected '228.6693056', error '0.0000000'

Test #32:

score: 0
Accepted
time: 1059ms
memory: 149824kb

input:

150
-1000000 149
-999832 148
-999483 147
-998973 146
-998277 145
-997405 144
-996353 143
-995120 142
-993712 141
-992141 140
-990389 139
-988460 138
-986361 137
-984063 136
-981574 135
-978908 134
-976051 133
-973002 132
-969790 131
-966386 130
-962811 129
-959055 128
-955095 127
-950958 126
-946662...

output:

223.9682054057

result:

ok found '223.9682054', expected '223.9682054', error '0.0000000'

Test #33:

score: 0
Accepted
time: 2483ms
memory: 258136kb

input:

200
-100000 199
-99990 198
-99973 197
-99950 196
-99917 195
-99878 194
-99828 193
-99773 192
-99709 191
-99634 190
-99550 189
-99451 188
-99339 187
-99218 186
-99087 185
-98945 184
-98797 183
-98640 182
-98472 181
-98295 180
-98109 179
-97914 178
-97705 177
-97484 176
-97249 175
-97010 174
-96763 17...

output:

309.8997066495

result:

ok found '309.8997066', expected '309.8997066', error '0.0000000'

Test #34:

score: 0
Accepted
time: 2492ms
memory: 258176kb

input:

200
-1000000 199
-999897 198
-999689 197
-999374 196
-998967 195
-998474 194
-997877 193
-997165 192
-996352 191
-995436 190
-994426 189
-993339 188
-992161 187
-990877 186
-989482 185
-987987 184
-986391 183
-984702 182
-982913 181
-981041 180
-979052 179
-976962 178
-974758 177
-972459 176
-970050...

output:

314.9777466520

result:

ok found '314.9777467', expected '314.9777467', error '0.0000000'

Test #35:

score: 0
Accepted
time: 4932ms
memory: 396944kb

input:

250
-100000 249
-99996 248
-99985 247
-99964 246
-99936 245
-99902 244
-99859 243
-99808 242
-99751 241
-99688 240
-99618 239
-99539 238
-99456 237
-99363 236
-99266 235
-99166 234
-99062 233
-98951 232
-98833 231
-98710 230
-98586 229
-98453 228
-98315 227
-98169 226
-98017 225
-97859 224
-97695 22...

output:

399.4986320702

result:

ok found '399.4986321', expected '399.4986321', error '0.0000000'

Test #36:

score: 0
Accepted
time: 4891ms
memory: 396396kb

input:

250
-1000000 249
-999934 248
-999801 247
-999608 246
-999369 245
-999064 244
-998687 243
-998240 242
-997733 241
-997171 240
-996542 239
-995856 238
-995110 237
-994305 236
-993438 235
-992507 234
-991500 233
-990427 232
-989296 231
-988091 230
-986826 229
-985493 228
-984101 227
-982644 226
-981122...

output:

408.8274918681

result:

ok found '408.8274919', expected '408.8274919', error '0.0000000'

Test #37:

score: 0
Accepted
time: 4849ms
memory: 397636kb

input:

250
1012 -227
343 -992
1002 -87
-870 555
873 591
-1086 -60
-803 749
-929 -519
295 968
-1029 95
-294 1013
584 -900
-396 -958
-409 -999
-593 -825
-1027 293
-779 640
527 916
-477 -966
996 210
998 -445
-368 961
-979 -406
-524 956
-1049 253
453 932
-139 -1021
-133 1065
-1046 -267
-1023 -95
928 532
-654 7...

output:

193.4349790772

result:

ok found '193.4349791', expected '193.4349791', error '0.0000000'

Test #38:

score: 0
Accepted
time: 4831ms
memory: 397188kb

input:

250
143722 184230
33550 199545
137314 167619
-96577 141269
-175447 -90690
-126133 -202209
154014 -114996
-11150 206860
-162751 -119108
-150322 -146422
-99463 203849
27378 -168853
187084 22360
33621 -206197
-143732 -174287
159 -206512
117429 -182707
137058 110908
-171210 136526
-159473 -158095
148141...

output:

212.9990280254

result:

ok found '212.9990280', expected '212.9990280', error '0.0000000'

Test #39:

score: 0
Accepted
time: 4821ms
memory: 397452kb

input:

250
626626 -779312
605865 -795564
-842260 539064
950763 -309899
-986761 -162159
-926795 -375562
-920043 -391795
-978775 -204924
-644497 -764602
-942293 -334762
-363961 931403
-50677 -998707
970402 -241482
433787 -901012
-715392 698714
781225 -624237
999951 8890
-962735 270436
951222 308490
69224 997...

output:

42.3916120159

result:

ok found '42.3916120', expected '42.3916120', error '0.0000000'

Test #40:

score: 0
Accepted
time: 5040ms
memory: 397036kb

input:

250
-158942 -61
304876 67
-596092 -66
482844 -44
-633328 -34
593703 44
-661509 71
-968180 7
778353 1
-521475 -30
-209606 43
-42053 -71
441684 47
-766779 54
-807390 45
-195820 8
-837797 -45
951843 -3
317166 68
-33704 53
-622182 -68
-138675 -35
698606 -57
-729950 33
407461 -13
932774 48
460886 20
5788...

output:

33.0801914586

result:

ok found '33.0801915', expected '33.0801915', error '0.0000000'

Test #41:

score: 0
Accepted
time: 5039ms
memory: 397840kb

input:

250
708342 124876
-80512 -14220
-540152 -95184
111356 19595
603631 106367
510458 89950
521299 91899
-503279 -88795
809350 142772
290612 51198
430591 75979
862973 152111
117294 20734
351214 61926
973724 171716
-605879 -106803
701401 123625
51040 8947
514762 90746
844509 148860
-110074 -19414
-647623 ...

output:

21.8110297327

result:

ok found '21.8110297', expected '21.8110298', error '0.0000000'

Test #42:

score: 0
Accepted
time: 5056ms
memory: 397880kb

input:

250
-36423 -36391
376553 376573
-608729 -608720
-92032 -92056
-706801 -706896
-139665 -139621
161123 161061
177889 177953
-62927 -62954
294950 295021
625107 625175
-706461 -706468
-691351 -691427
17510 17472
58280 58375
-415119 -415018
-214773 -214749
-349385 -349456
269764 269788
-286580 -286478
-6...

output:

22.1496892597

result:

ok found '22.1496893', expected '22.1496893', error '0.0000000'

Test #43:

score: 0
Accepted
time: 5056ms
memory: 397728kb

input:

250
55 573829
-14 631752
-64 858230
-25 197383
-60 -282104
-59 -751316
-1 -550029
59 814047
-29 -667326
-21 627945
62 517683
-38 242783
-25 953304
60 -46838
-1 -667346
68 -438210
-37 647066
-43 -334803
-40 -431209
-17 -129153
-28 828537
23 864960
52 -212667
-8 539728
-32 -692614
-65 742212
-29 -5901...

output:

22.8372773507

result:

ok found '22.8372774', expected '22.8372774', error '0.0000000'

Test #44:

score: 0
Accepted
time: 5065ms
memory: 397900kb

input:

250
110181 -624551
120920 -685980
97225 -551019
135896 -770962
79288 -449606
120040 -681113
76344 -433072
-40239 227871
-91741 520483
-74254 420892
44816 -254592
16454 -93431
148766 -843459
40657 -230618
-41985 237995
88737 -503000
-26845 152473
-131441 745296
-94734 537210
138467 -785413
-173125 98...

output:

17.4040898665

result:

ok found '17.4040899', expected '17.4040899', error '0.0000000'

Test #45:

score: 0
Accepted
time: 4642ms
memory: 396200kb

input:

250
7735 -743271
-162493 -185341
-8634 968279
740236 -501470
-332764 -553470
-120802 -788998
-8302 968847
-472452 -748840
-715302 -872153
-440493 113659
7176 -743284
875366 -263721
-697824 -612284
-332258 -553224
-423824 -144284
-341287 -327384
-595668 -234804
138735 -525271
-595645 -234042
-715158 ...

output:

137.5248268652

result:

ok found '137.5248269', expected '137.5248269', error '0.0000000'

Test #46:

score: 0
Accepted
time: 4755ms
memory: 396568kb

input:

250
-369729 205979
-278536 125664
-344133 -71646
84554 408373
-374550 204949
-176125 8135
173852 -258661
-280457 126236
414492 18741
-175330 9282
-219033 366207
-279817 128753
-178998 -273067
-126442 253722
83781 408976
415906 17269
-257221 265138
-175328 6160
-370363 201020
-347390 -72083
-130110 2...

output:

298.4506039902

result:

ok found '298.4506040', expected '298.4506040', error '0.0000000'

Test #47:

score: 0
Accepted
time: 4644ms
memory: 396452kb

input:

250
47929 4788
35860 -79527
-120083 117342
-115403 -97704
-143971 -98248
-60199 115628
34357 -103554
-121786 -120977
-146590 132913
159556 131188
-49082 -80931
-89195 46440
-159386 -46652
56567 -82102
-12508 33697
-21236 -95439
-103370 167109
-115468 -97811
130043 16412
-77630 -126093
128659 89028
-...

output:

176.6284116385

result:

ok found '176.6284116', expected '176.6284116', error '0.0000000'

Test #48:

score: 0
Accepted
time: 4608ms
memory: 396884kb

input:

250
827789 421308
106029 -890822
-108874 -140593
354733 -20775
-109751 -137462
177103 -352125
308053 -356605
472446 295377
354739 -20772
545012 633541
-669554 157147
-109757 -137465
-540611 -361342
-136729 299596
-555911 593728
888973 -453205
-555917 593725
-619449 -324104
-447984 317437
-181249 -33...

output:

181.1215200390

result:

ok found '181.1215200', expected '181.1215200', error '0.0000000'

Test #49:

score: 0
Accepted
time: 4827ms
memory: 397016kb

input:

250
936092 353880
784375 -657402
86466 944543
177185 -867808
326305 108607
983092 -586120
-707695 907607
-390625 329598
984305 -502393
795092 447880
173375 -892402
929185 119192
43092 -915120
-625625 376598
737375 141598
697466 850543
466092 -727120
-708908 635880
-101534 850543
-61625 940598
467305...

output:

383.2345363147

result:

ok found '383.2345363', expected '383.2345363', error '0.0000000'

Test #50:

score: 0
Accepted
time: 4789ms
memory: 396552kb

input:

250
-118569 -140749
-97422 -138838
-97375 -138627
-26090 118921
206869 -128921
-97404 -139079
-97033 -139104
206798 -128463
-25769 119134
-96894 -138968
172814 6500
206910 -128995
172798 6616
207159 -128601
-119198 -140960
206410 -128494
173240 6756
206512 -129116
-26002 119194
173478 6701
-96966 -1...

output:

67.5759896055

result:

ok found '67.5759896', expected '67.5759896', error '0.0000000'

Test #51:

score: 0
Accepted
time: 4778ms
memory: 397408kb

input:

250
-229871 727747
503120 660957
279164 -642944
148490 355617
503129 660947
503155 660921
-229877 727747
586885 348612
503158 660957
503149 660944
503149 660954
148484 355635
503120 660944
148518 355612
279174 -642926
586892 348602
-229854 727758
279181 -642939
-229865 727724
503138 660927
279187 -6...

output:

273.9749093956

result:

ok found '273.9749094', expected '273.9749094', error '0.0000000'

Test #52:

score: 0
Accepted
time: 4835ms
memory: 397928kb

input:

250
-448301 -23731
-757738 -414145
-826693 9197
-780743 -422219
-364443 -750631
-796220 -399015
-733092 -418855
-429839 -7644
-444665 -734294
-742340 -386318
-894763 83520
-617532 -849423
-733014 -417877
-789839 -367644
-440192 -765342
-420743 -62219
-394340 -50750
-429665 -46226
-890192 44658
-8410...

output:

183.1873980915

result:

ok found '183.1873981', expected '183.1873981', error '0.0000000'

Test #53:

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

input:

10
-929 -967
-970 -298
-965 360
-958 923
-296 -957
-337 -342
-311 292
-281 975
342 -955
283 -276

output:

19.8182749094

result:

ok found '19.8182749', expected '19.8182749', error '0.0000000'

Test #54:

score: 0
Accepted
time: 288ms
memory: 40132kb

input:

100
-994805 -999938
-996110 -782089
-992919 -573100
-995504 -360728
-992492 -155059
-999396 58200
-995106 269969
-996198 485840
-992862 691285
-999137 905512
-782070 -995961
-787601 -782785
-787156 -575414
-786172 -359796
-781311 -153646
-783933 63971
-783933 274829
-781370 480656
-787605 691837
-78...

output:

859.5346034145

result:

ok found '859.5346034', expected '859.5346034', error '0.0000000'

Test #55:

score: 0
Accepted
time: 1027ms
memory: 149156kb

input:

150
-998502 -999099
-999398 -839150
-998946 -682207
-999717 -523880
-997476 -365420
-999676 -208175
-998634 -47490
-997463 108832
-999252 267688
-998303 427690
-999727 584993
-998548 743468
-997534 902770
-838514 -998825
-838915 -839245
-838761 -681004
-840029 -522233
-841142 -366005
-841333 -207461...

output:

1631.7295261343

result:

ok found '1631.7295261', expected '1631.7295261', error '0.0000000'

Test #56:

score: 0
Accepted
time: 2488ms
memory: 258384kb

input:

200
-998883 -999122
-999739 -863888
-998648 -728163
-998654 -592077
-998857 -456655
-999478 -320991
-999687 -184933
-999447 -49787
-999310 85778
-999163 221451
-999121 358265
-999827 493143
-999266 629360
-999588 765471
-999945 900699
-864070 -998957
-862933 -863164
-863564 -728065
-863308 -591976
-...

output:

2556.7563001614

result:

ok found '2556.7563002', expected '2556.7563002', error '0.0000000'

Test #57:

score: 0
Accepted
time: 4919ms
memory: 397664kb

input:

250
-999494 -999544
-999973 -872086
-999464 -745600
-999441 -619250
-999738 -492789
-998888 -365897
-999365 -239432
-999677 -112880
-999626 13457
-999460 140280
-998934 267634
-999098 393706
-999720 520895
-999132 647797
-999369 774589
-998920 900467
-872613 -999663
-873317 -872283
-873066 -746144
-...

output:

3597.9060013911

result:

ok found '3597.9060014', expected '3597.9060014', error '0.0000000'