QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791227#9728. Catch the Starskip2004AC ✓306ms35664kbC++203.2kb2024-11-28 17:34:552024-11-28 17:34:57

Judging History

This is the latest submission verdict.

  • [2024-11-28 17:34:57]
  • Judged
  • Verdict: AC
  • Time: 306ms
  • Memory: 35664kb
  • [2024-11-28 17:34:55]
  • Submitted

answer

#include<bits/stdc++.h>
using std::cin, std::cout;
using db = long double;
using f128 = __float128;
using ll = long long;
const db eps = 1e-12;
struct p2 {
	db x, y;
	db abs() {
		return sqrt(x * x + y * y);
	}
};
p2 operator - (p2 x, p2 y) {
	return {x.x - y.x, x.y - y.y};
}
db operator * (p2 x, p2 y) {
	return x.x * y.y - x.y * y.x;
}
p2 findmin(std::vector<p2> & a, auto cmp) {
	int l = 0, r = a.size() - 1, d = 1;
	if(cmp(a.back(), a[0])) std::swap(l, r), d = -1;
	for(;(r - l) * d > 1;) {
		int mid = (l + r) >> 1;
		if(cmp(a[mid], a[mid - d]) && cmp(a[mid], a[l])) {
			l = mid;
		} else {
			r = mid;
		}
	}
	return a[l];
}
const int N = 500005;
std::vector<p2> star, moon[N];
std::vector<p2> read() {
	int n; cin >> n;
	std::vector<p2> a(n);
	for(int i = 0;i < n;++i) {
		int x, y; cin >> x >> y;
		a[i] = {x, y};
	}
	return a;
}

p2 r90(p2 x) {
	return {-x.y, x.x};
}
struct line : p2 {
	db z;
	line(p2 a, p2 b) : p2(r90(b - a)), z(a * b) {}
};
using i128 = __int128;
struct frac {
	ll u, v;
	frac(ll A, ll B = 1) {
		u = A, v = B;
		if(v < 0) u *= -1, v *= -1;
	}
	bool operator == (const frac & b) const {
		return (i128) u * b.v == (i128) v * b.u;
	}
	bool operator < (const frac & b) const {
		return (i128) u * b.v < (i128) b.u * v;
	}
	f128 val() const {
		return (f128) u / v;
	}
};
int n;
db l, r;
void solve() {
	cin >> n >> l >> r;
	star = read();
	for(int i = 0;i < n;++i) {
		moon[i] = read();
	}
	std::vector<std::pair<frac, int>> o;
	o.emplace_back(frac(l), 1);
	o.emplace_back(frac(r), -1);
	for(int i = 0;i < n;++i) {
		p2 u[2], v[2];
		auto & A = star, & B = moon[i];
		for(int s = 0;s < 2;++s) {
			p2 S;
			int sgn = s ? 1 : -1;
			auto cmp0 = [&](p2 x, p2 y) {
				return (x - S) * (y - S) * sgn > 0;
			};
			auto cmp1 = [&](p2 x, p2 y) {
				S = x; p2 u = findmin(B, cmp0);
				S = y; p2 v = findmin(B, cmp0);
				return (u - x) * (v - y) * sgn > 0;
			};
			S = u[s] = findmin(A, cmp1), v[s] = findmin(B, cmp0);
		}
		frac L = l - 1, R = r + 1;
		auto add = [&](p2 u, p2 v) {
			line li(u, v);
			if(fabs(li.x) < eps) {
				if(li.z < eps) {
					L = r + 1, R = l;
				}
			} else {
				if(li.x > 0) {
					L = std::max(L, frac(-li.z, li.x));
				} else {
					R = std::min(R, frac(-li.z, li.x));
				}
			}
		};
		add(v[0], u[0]);
		add(u[1], v[1]);
		if((v[0] - v[1]).abs() > 1e-9) {
			add(v[0], v[1]);
		}
		if(L < R) {
			o.emplace_back(L, -1);
			o.emplace_back(R, 1);
		}
	}
	db ans = 0;
	sort(o.begin(), o.end(), [](auto x, auto y) {
		auto [x0, x1] = x;
		auto [y0, y1] = y;
		if(x0 == y0) {
			return x1 > y1;
		}
		return x0 < y0;
	});
	int count = 0, ok = 0;
	for(int i = 0;i + 1 < (int) o.size();++i) {
		count += o[i].second;
		if(count > 0) {
		  
			ans += o[i + 1].first.val() - o[i].first.val();
			if(o[i + 1].first == o[i].first) {
			  if(o[i].first == frac(l)) continue;
			  if(o[i].first == frac(r)) continue;
			}
			ok = 1;
		}
	}
	if(ok) {
		printf("%.13Lf\n", ans);
	} else {
		puts("-1");
	}

}
int main() {
//	freopen("1.in", "r", stdin);
	std::ios::sync_with_stdio(false), cin.tie(0);
	int T; cin >> T;
	for(int i = 0;i < T;++i) {
		solve();
	}
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
4 -8 8
3 -7 7 -6 8 -7 8
3 -9 -2 -7 3 -9 -1
3 -2 3 0 2 -4 5
3 5 1 5 3 4 2
3 1 -1 2 -2 3 -1
5 -8 8
5 -14 -3 -10 -2 -9 2 -10 4 -12 5
3 -16 0 -15 0 -15 1
3 -15 6 -9 5 -15 7
3 -10 5 -9 5 -10 6
3 -7 3 -3 2 -8 4
3 -6 -1 -6 -2 -5 -1

output:

9.4047619047619
6.0000000000000

result:

ok 2 numbers

Test #2:

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

input:

3
1 -4 4
3 -2 6 0 5 2 6
3 -3 1 3 1 0 4
3 -2 2
3 -2 4 2 4 0 6
3 -2 2 -1 2 -2 3
3 1 2 2 2 2 3
3 -2 -1 0 -3 2 -1
1 1 2
3 -8 0 -7 0 -8 1
3 -5 0 -4 -1 -4 0

output:

-1
0.0000000000000
1.0000000000000

result:

ok 3 numbers

Test #3:

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

input:

1
1 -744567334 955216804
5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600
5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -393010201 -131854694

output:

1699779738.6919791923137

result:

ok found '1699779738.691979170', expected '1699779738.691979170', error '0.000000000'

Test #4:

score: 0
Accepted
time: 42ms
memory: 3760kb

input:

16666
2 -732787031 -732787030
3 -798263477 735869144 -583647039 529057159 -583647039 529057160
3 -777230180 499482549 -777230181 499482549 -777230180 499482548
3 -661853868 251627327 -661853868 251627326 -661853867 251627327
2 463140451 463140452
3 232604219 637008523 797038205 345997813 797038205 3...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 16666 numbers

Test #5:

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

input:

16667
2 -9 7
3 -8 4 -6 1 -4 2
3 6 13 2 12 3 10
3 -1 7 0 10 -3 4
2 -9 5
3 -8 10 -5 8 -4 10
3 10 -8 9 -11 12 -8
3 -10 -5 -8 -4 -7 -1
2 -6 5
3 -8 6 -7 6 -5 7
3 -2 -3 1 -4 -4 -2
3 1 10 0 10 -1 8
2 -9 9
3 -5 -11 -2 -11 -5 -8
3 6 -5 5 -2 4 -5
3 11 6 9 3 11 3
2 -6 5
3 -7 6 -8 7 -9 4
3 9 2 12 -3 11 0
3 -6 3...

output:

16.0000000000000
14.0000000000000
11.0000000000000
15.5555555555556
-1
12.0000000000000
14.0000000000000
17.0000000000000
11.0000000000000
16.0000000000000
11.0000000000000
15.0000000000000
15.0000000000000
10.0000000000000
18.0000000000000
16.0000000000000
14.0000000000000
17.0000000000000
12.00000...

result:

ok 16667 numbers

Test #6:

score: 0
Accepted
time: 42ms
memory: 3856kb

input:

16667
2 -6 10
3 6 -8 8 -10 9 -7
3 -5 13 -6 10 -6 8
3 8 10 7 7 10 7
2 -8 7
3 2 -10 0 -12 3 -11
3 -6 -7 -3 -5 -4 -4
3 10 -3 8 -3 8 -6
2 -7 6
3 9 1 9 4 6 1
3 7 -6 4 -8 6 -8
3 -3 -12 -4 -10 -5 -14
2 -10 10
3 11 -4 9 -1 9 -3
3 -6 -7 -6 -8 -5 -5
3 -10 -7 -7 -10 -6 -10
2 -9 8
3 3 2 3 1 6 5
3 4 -2 0 -3 1 -3...

output:

16.0000000000000
12.1428571428571
13.0000000000000
20.0000000000000
17.0000000000000
13.0000000000000
15.0000000000000
16.0000000000000
19.0000000000000
11.0000000000000
15.0000000000000
20.0000000000000
15.0000000000000
-1
14.0000000000000
19.0000000000000
17.0000000000000
13.0000000000000
13.00000...

result:

ok 16667 numbers

Test #7:

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

input:

16667
2 -20 15
3 17 -17 22 -14 14 -16
3 -5 -12 -3 -8 -8 -12
3 11 8 15 10 8 8
2 -10 12
3 -14 -13 -19 -9 -11 -17
3 14 13 10 12 14 9
3 -5 -20 -7 -17 -7 -20
2 -11 10
3 0 -24 -1 -20 -5 -19
3 -12 -2 -15 -5 -12 -5
3 10 -21 14 -24 14 -19
2 -15 20
3 -3 -16 -4 -10 -6 -15
3 8 17 7 12 10 17
3 8 -7 10 -5 11 -3
2...

output:

35.0000000000000
22.0000000000000
21.0000000000000
29.2307692307692
31.0000000000000
37.0000000000000
17.2500000000000
38.0000000000000
37.0000000000000
31.0000000000000
30.0000000000000
33.0000000000000
27.0000000000000
30.0000000000000
30.0000000000000
31.0000000000000
16.4285714285714
24.87500000...

result:

ok 16667 numbers

Test #8:

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

input:

16667
2 -19 19
3 18 -12 22 -15 20 -12
3 24 0 20 2 20 -3
3 15 25 18 20 19 22
2 -18 20
3 10 6 11 11 7 8
3 26 -21 20 -12 21 -17
3 -4 -13 -11 -19 -6 -18
2 -13 14
3 19 -4 20 0 17 -7
3 1 -8 6 -12 3 -7
3 12 -7 5 -2 10 -6
2 -18 12
3 14 -5 15 -6 17 -4
3 18 -20 15 -19 20 -22
3 14 -8 18 -3 12 -10
2 -14 15
3 17...

output:

38.0000000000000
38.0000000000000
13.8000000000000
30.0000000000000
29.0000000000000
25.0000000000000
27.0000000000000
27.0000000000000
29.0000000000000
28.0000000000000
27.0000000000000
34.0000000000000
35.0000000000000
20.0000000000000
20.0000000000000
25.0000000000000
25.0000000000000
38.00000000...

result:

ok 16667 numbers

Test #9:

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

input:

8334
5 -17 14
5 -9 13 -12 15 -15 10 -15 9 -13 9
5 24 4 22 9 17 13 20 8 23 4
4 -11 4 -12 6 -17 9 -14 6
5 -7 23 -10 19 -10 17 -1 23 -3 28
4 23 -16 20 -11 15 -7 11 -11
5 15 -9 14 -9 15 -12 19 -14 20 -10
5 -11 10
5 -4 8 -1 10 -13 16 -14 15 -9 11
5 9 2 12 5 14 10 2 4 4 1
5 20 -12 23 -15 29 -10 27 -9 22 -...

output:

20.0000000000000
15.0000000000000
34.0000000000000
21.0000000000000
25.0000000000000
21.0000000000000
21.0000000000000
35.0000000000000
6.3333333333333
32.0000000000000
28.0000000000000
-1
25.0000000000000
30.0000000000000
38.0000000000000
35.0000000000000
8.9166666666667
17.5333333333333
23.8461538...

result:

ok 8334 numbers

Test #10:

score: 0
Accepted
time: 47ms
memory: 3864kb

input:

8334
5 -10 19
5 28 13 20 10 24 8 28 8 29 13
5 -5 24 -5 20 -1 19 4 22 -1 24
5 -15 11 -10 8 -9 8 -12 13 -14 16
5 -4 16 -5 11 -1 16 -1 18 -2 21
3 12 21 13 13 17 18
4 -19 7 -15 10 -19 14 -20 12
5 -19 10
5 17 10 14 10 11 8 10 6 11 4
3 -5 -2 -10 -7 -5 -12
4 18 -4 20 -1 20 2 15 -3
4 -16 -4 -20 -5 -16 -9 -1...

output:

29.0000000000000
29.0000000000000
27.0000000000000
35.0000000000000
35.0000000000000
27.0000000000000
33.0000000000000
33.4000000000000
8.5000000000000
34.0000000000000
29.0000000000000
29.0000000000000
29.0000000000000
12.0000000000000
23.0000000000000
3.5000000000000
30.0000000000000
13.7142857142...

result:

ok 8334 numbers

Test #11:

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

input:

8334
5 -24 23
5 -2 -9 -8 -9 -5 -13 0 -14 1 -10
3 -15 -8 -10 -4 -16 -7
5 0 -45 1 -45 5 -41 4 -40 -2 -43
3 8 32 9 27 12 30
5 33 1 36 -2 41 1 43 4 32 6
5 5 -35 7 -34 5 -30 1 -30 -2 -33
5 -38 33
5 44 29 39 34 35 35 36 34 41 30
5 29 25 32 20 36 18 37 22 31 27
4 29 15 33 12 38 12 33 17
5 -33 -29 -33 -30 -...

output:

34.6000000000000
-1
63.0000000000000
25.0000000000000
47.7500000000000
52.8235294117647
49.0000000000000
62.0000000000000
50.5517241379310
42.0000000000000
39.0000000000000
63.0000000000000
38.8181818181818
37.7368421052632
58.0000000000000
2.3333333333333
51.6363636363636
52.0000000000000
28.142857...

result:

ok 8334 numbers

Test #12:

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

input:

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

output:

57.7142857142857
48.0000000000000
55.0000000000000
59.0000000000000
52.6666666666667
54.3125000000000
65.0000000000000
40.0404858299595
5.1428571428571
32.9411764705882
61.0000000000000
41.0000000000000
58.8260869565217
57.0000000000000
9.1875000000000
66.0000000000000
68.6428571428571
52.1000000000...

result:

ok 8334 numbers

Test #13:

score: 0
Accepted
time: 91ms
memory: 3852kb

input:

8334
5 -27 34
10 -34 40 -35 39 -39 31 -40 27 -35 25 -30 26 -28 30 -27 33 -27 37 -31 39
9 19 20 21 24 19 29 17 29 16 28 7 16 9 12 13 11 16 15
6 1 -20 7 -28 11 -29 12 -26 10 -22 6 -17
10 40 -48 42 -45 43 -40 39 -36 35 -35 30 -37 28 -40 28 -45 30 -48 35 -50
7 44 -3 49 0 51 2 50 7 48 10 43 5 39 0
8 20 -...

output:

53.2800000000000
59.0000000000000
71.0000000000000
59.0000000000000
11.0000000000000
47.0000000000000
4.6000000000000
41.7333333333333
71.0000000000000
17.7307692307692
46.3529411764706
70.0000000000000
43.9393939393939
-1
44.0000000000000
43.0000000000000
61.2857142857143
49.0000000000000
36.321428...

result:

ok 8334 numbers

Test #14:

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

input:

8334
5 -20 29
10 32 17 27 20 25 20 20 16 26 6 31 5 32 5 36 6 37 9 36 14
7 -28 29 -28 33 -32 32 -37 29 -40 27 -37 26 -32 25
7 39 23 36 26 33 28 31 29 28 27 30 22 32 18
8 1 13 5 13 6 17 4 22 0 26 -4 24 -5 19 -3 15
8 -26 28 -23 23 -19 25 -15 29 -13 34 -23 36 -27 36 -27 33
8 4 39 2 38 -2 33 -2 32 0 27 3...

output:

49.0000000000000
51.0000000000000
55.0000000000000
-1
59.0000000000000
23.2666666666667
40.5384615384615
34.1351351351351
28.4000000000000
73.0000000000000
54.0526315789474
59.0000000000000
18.1666666666667
66.0000000000000
-1
-1
48.0000000000000
50.0000000000000
13.0909090909091
60.0000000000000
55...

result:

ok 8334 numbers

Test #15:

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

input:

8334
5 -3126 3527
40 2524 -3205 2555 -3204 2565 -3202 2571 -3200 2573 -3199 2582 -3194 2590 -3189 2593 -3187 2597 -3182 2603 -3174 2608 -3164 2610 -3159 2612 -3149 2611 -3139 2608 -3134 2606 -3132 2598 -3125 2588 -3120 2583 -3118 2575 -3115 2565 -3112 2555 -3110 2553 -3110 2544 -3111 2538 -3112 2528...

output:

6508.6952604778692
6121.0000000000000
5228.1460508798402
7545.0000000000000
6439.3016849047579
5552.0000000000000
7258.0000000000000
4340.0000000000000
7161.0000000000000
6347.0000000000000
6490.5694214299380
7132.5504540480350
5888.7560530761356
5827.0000000000000
4107.0000000000000
5813.0000000000...

result:

ok 8334 numbers

Test #16:

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

input:

8334
5 -2274 2353
40 2604 1999 2602 1992 2601 1985 2601 1984 2603 1974 2606 1965 2610 1955 2613 1948 2623 1940 2633 1938 2636 1939 2644 1944 2651 1949 2660 1956 2713 2008 2718 2015 2721 2021 2720 2031 2719 2040 2718 2048 2717 2051 2713 2060 2708 2070 2698 2078 2692 2080 2685 2082 2676 2083 2672 2082...

output:

4298.5496256600680
5799.0000000000000
4987.3650513097115
7308.0000000000000
5589.7037603482210
4652.0000000000000
6082.1417461463489
6086.0000000000000
3355.7661445033507
6459.0000000000000
6291.0000000000000
4838.0000000000000
4464.1806120253332
6093.0000000000000
6359.0000000000000
5211.0037287842...

result:

ok 8334 numbers

Test #17:

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

input:

2274
5 -29040 32893
40 21293 3672 21285 3680 21278 3685 21271 3688 21266 3690 21258 3693 21255 3694 21254 3694 21245 3693 21239 3692 21223 3687 21218 3684 21214 3680 21208 3673 21203 3667 21198 3659 21195 3650 21193 3643 21191 3633 21194 3624 21198 3616 21203 3609 21211 3600 21220 3590 21221 3589 21...

output:

61933.0000000000000
35500.5000000000000
49406.0000000000000
67961.0667302496077
54610.0000000000000
63846.0000000000000
54004.0000000000000
48450.5433992260645
48956.3327586530873
60754.0000000000000
62140.8779092105161
68347.6515318155751
68003.0398516064853
57584.0000000000000
56121.0000000000000
...

result:

ok 2274 numbers

Test #18:

score: 0
Accepted
time: 127ms
memory: 3884kb

input:

2271
5 -21608 38109
40 3288 29821 3282 29828 3277 29833 3268 29840 3258 29846 3256 29847 3250 29849 3240 29852 3233 29854 3228 29855 3220 29856 3218 29856 3212 29855 3210 29854 3205 29851 3197 29846 3189 29840 3179 29831 3176 29827 3171 29820 3165 29811 3163 29807 3160 29797 3167 29789 3172 29784 31...

output:

59717.0000000000000
62108.0000000000000
57257.0000000000000
66813.3893155625352
65446.0000000000000
59441.1599608461894
55000.0000000000000
70062.3676427178812
61092.7222705071350
62176.0000000000000
58821.0000000000000
55055.6726098528661
52351.0000000000000
63396.8802584199081
51497.0000000000000
...

result:

ok 2271 numbers

Test #19:

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

input:

1997
5 -685963307 853750511
100 372319561 823923262 372319594 823923310 372319621 823923350 372319653 823923400 372319681 823923445 372319710 823923492 372319721 823923511 372319739 823923548 372319750 823923572 372319764 823923603 372319780 823923639 372319785 823923651 372319795 823923692 37231980...

output:

1539712423.4948485301575
1259604092.0000000000000
1674868892.0000000000000
1100380125.0000000000000
1314807604.0000000000000
1476460075.0000000000000
1657770700.0000000000000
1681539925.0000000000000
1479119212.0000000000000
1631814313.2232183826854
1480527084.0000000000000
1718090694.0000000000000
...

result:

ok 1997 numbers

Test #20:

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

input:

1998
5 -923518671 909017531
100 921654169 61734551 921654198 61734600 921654221 61734644 921654467 61735150 921654480 61735178 921654498 61735219 921654513 61735254 921654521 61735279 921654530 61735323 921654538 61735365 921654541 61735403 921654531 61735447 921654520 61735489 921654511 61735514 92...

output:

1832536202.0000000000000
1443062393.5536196638132
1680030554.0000000000000
1744446320.9300861220108
1205113181.0000000000000
1326796808.0000000000000
1213723402.1944884834811
1578305206.6213288727449
1334732988.9588083283743
1129359860.2188185728155
1542969200.0000000000000
1183125071.7464432109846
...

result:

ok 1998 numbers

Test #21:

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

input:

8334
5 -744567334 955216804
5 -781518205 -852078097 -781516900 -852078384 -781516392 -852076569 -781518329 -852076047 -781519925 -852077600
3 871916993 -588891734 871918253 -588892444 871918745 -588891234
5 -393011614 -131855702 -393010699 -131856607 -393008846 -131856475 -393009388 -131854587 -3930...

output:

1699779738.6919791923137
1527796251.0902726690983
1655793192.9268333420623
1672892305.0000000000000
1368134291.0000000000000
1463897904.0000000000000
1363175149.0000000000000
1296404984.0000000000000
1424194359.0000000000000
1029663073.0000000000000
1778254477.0000000000000
1503717633.0000000000000
...

result:

ok 8334 numbers

Test #22:

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

input:

8334
5 -829825735 601784461
5 714610651 -975306485 714610404 -975306399 714609317 -975307983 714610491 -975308230 714610739 -975307741
5 -478043159 166470433 -478042674 166466411 -478041707 166468042 -478041795 166469844 -478042741 166471670
5 -574496064 117824476 -574497244 117826229 -574498481 117...

output:

1431606742.6004441381665
1730324827.0000000000000
1908650236.1184175573289
1890778564.0000000000000
1340666568.0000000000000
1319811364.0000000000000
1421853075.0000000000000
1490477103.0000000000000
1873755437.0000000000000
1570402518.0000000000000
1395074328.0000000000000
1612895854.0000000000000
...

result:

ok 8334 numbers

Test #23:

score: 0
Accepted
time: 99ms
memory: 3868kb

input:

8334
5 -913048220 656325022
10 -166143242 -673183677 -166142264 -673184186 -166140797 -673184088 -166139127 -673183351 -166137499 -673182562 -166137324 -673182139 -166138589 -673181699 -166140193 -673181144 -166141964 -673181446 -166142469 -673181967
6 -945075435 650359787 -945076678 650360341 -9450...

output:

1569349415.9143458922626
1880676443.0000000000000
1316771742.0000000000000
1107991785.0000000000000
1549997697.4441737241577
1824059958.0000000000000
1444570056.0000000000000
1418459383.0000000000000
1505112947.0000000000000
1326424768.4310334007023
1369086579.0000000000000
1304632569.0148523682728
...

result:

ok 8334 numbers

Test #24:

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

input:

8334
5 -894419066 986206278
10 438340992 -480519836 438342647 -480520761 438343571 -480520315 438344403 -480519603 438345824 -480518172 438346510 -480516618 438345277 -480515164 438343852 -480515669 438342447 -480516557 438340542 -480518404
10 -240550387 -258562092 -240551334 -258563442 -240550967 -...

output:

1880625344.0000000000000
1466897680.3373602151405
1494132112.2832910474390
1408363298.6958165680990
1390133394.0000000000000
1485867441.4218668231042
1590839506.0000000000000
1556522174.3443128587678
1614474976.0000000000000
1231693774.0000000000000
1493791516.0000000000000
1294379747.0000000000000
...

result:

ok 8334 numbers

Test #25:

score: 0
Accepted
time: 147ms
memory: 3876kb

input:

2004
5 -851485863 922356807
100 806952389 -620838027 806952796 -620839051 806952929 -620839348 806953823 -620841099 806955255 -620843002 806956607 -620844576 806958351 -620846452 806958738 -620846812 806960698 -620848575 806962485 -620850179 806964065 -620851590 806965685 -620852945 806966771 -62085...

output:

1773665579.3962146450067
1245647086.0000000000000
1698103416.9895664505893
1192937188.0000000000000
1495810673.0000000000000
1331670703.0532930288464
1550766126.0000000000000
1572739123.0000000000000
1403505529.7508068775060
1564997181.0000000000000
1537044013.0000000000000
1092166901.0000000000000
...

result:

ok 2004 numbers

Test #26:

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

input:

2001
5 -807916374 951640620
100 471800611 -609005450 471800882 -609005598 471802784 -609006412 471803897 -609006871 471804858 -609007255 471806094 -609007726 471807518 -609008221 471808084 -609008358 471830663 -609011338 471831366 -609011271 471832821 -609011131 471834532 -609010816 471835066 -60901...

output:

1759556994.0000000000000
1438355564.0000000000000
1162987446.0000000000000
1473770184.0000000000000
1660711599.3048792488407
1258059674.0000000000000
1509519860.0000000000000
1502232261.3515482684597
1622595242.0000000000000
1116409602.0000000000000
1497870504.0000000000000
1707338453.0000000000000
...

result:

ok 2001 numbers

Test #27:

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

input:

10000
4 -876359283 597412519
84 -787103890 -543670676 -787103889 -543670617 -787103891 -543670566 -787103894 -543670542 -787103904 -543670486 -787103936 -543670413 -787103965 -543670352 -787104009 -543670286 -787104058 -543670216 -787104095 -543670169 -787104166 -543670087 -787104201 -543670047 -787...

output:

1473771802.0000000000000
1184445109.0000000000000
1273369968.0000000000000
1842104023.1491100040730
1401842961.3655047668144
1220676735.0000000000000
1584003979.0000000000000
1936415212.6036023122724
1439576635.0000000000000
1536198292.0000000000000
1744272262.9695435302565
1361024307.0000000000000
...

result:

ok 10000 numbers

Test #28:

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

input:

10000
4 -514589336 681051743
84 260136457 -778772788 260136398 -778772766 260136148 -778772704 260136080 -778772696 260135984 -778772691 260135939 -778772690 260135861 -778772692 260135765 -778772698 260135685 -778772707 260135618 -778772723 260135537 -778772753 260135478 -778772779 260135382 -77877...

output:

1195641079.0000000000000
1569912356.0000000000000
1518856735.0000000000000
1342714391.0000000000000
1214213079.0000000000000
1283220624.0000000000000
1796134134.9315106974682
1801713431.0000000000000
1728469471.0000000000000
1970762015.0000000000000
1597570818.4290186666185
1543786958.0000000000000
...

result:

ok 10000 numbers

Test #29:

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

input:

10000
4 -854654469 777152266
84 -384437137 684560566 -384431810 684557290 -384422840 684552374 -384419937 684550899 -384413227 684547586 -384405159 684543922 -384396194 684540151 -384388285 684537901 -384381318 684537075 -384371666 684537161 -384370437 684537184 -384360706 684539373 -384351311 68454...

output:

1631806735.0000000000000
1424123468.0000000000000
1389677992.9187742940849
1576800025.0000000000000
1598916583.0000000000000
1464498679.0000000000000
1442804058.0000000000000
1666175099.0000000000000
1255050820.5701573814731
1561177121.7347437439021
1064468001.8450475030695
1105635482.0000000000000
...

result:

ok 10000 numbers

Test #30:

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

input:

10000
4 -771015246 658891315
84 45385710 -738165668 45385885 -738161269 45383143 -738154169 45381155 -738149591 45376641 -738139660 45372989 -738132856 45368735 -738126806 45366451 -738123774 45362745 -738119336 45356788 -738112594 45349125 -738104101 45342610 -738097460 45340181 -738095044 45333803...

output:

1429897974.6089238909772
1599820440.0000000000000
1236214920.0000000000000
1209017337.6775358885061
1873859588.0000000000000
1497435375.6426767837256
1478507602.0000000000000
1482210060.0000000000000
1260810353.9148009242490
1951395191.1792613106081
1753080128.4497046860633
1585952534.0000000000000
...

result:

ok 10000 numbers

Test #31:

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

input:

10000
4 -674914723 624418103
84 468468889 -499756104 468162339 -498888072 467601497 -497899887 466878219 -497038435 466134518 -496365273 465159179 -495560087 464211972 -495044122 464079613 -494973564 452212861 -493825380 452065957 -493824296 451407015 -493875285 450463932 -494062942 449543371 -49428...

output:

1264072929.7616702276282
1254262766.0000000000000
1663984089.0000000000000
1010711694.6540352136362
1470813291.0000000000000
1650827665.8829987841891
1254261966.0000000000000
1831622248.0000000000000
1374140339.0000000000000
1281253922.2480640101712
1567809316.0000000000000
1399880736.4704074321780
...

result:

ok 10000 numbers

Test #32:

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

input:

10000
4 -793175674 721626772
84 159345272 608883920 159698008 608015757 160118829 607278757 160699965 606292987 161301597 605353770 161836414 604600518 162258566 604103305 163119033 603125136 163652511 602547566 164390150 601772176 164814728 601358247 165571440 600703011 166011409 600345459 16678223...

output:

1504659632.6815229952335
1455208210.0000000000000
1338582258.1459399627056
1165325420.6774965829682
1454903090.0000000000000
1213494640.0000000000000
1777063188.0000000000000
1517563822.7316181815695
1068984015.0000000000000
1565287784.0000000000000
1375082267.0000000000000
1360915571.0000000000000
...

result:

ok 10000 numbers

Test #33:

score: 0
Accepted
time: 115ms
memory: 5488kb

input:

5
10000 -525096166 506746434
3000 528096060 105801840 528097856 105801473 528099429 105801157 528100970 105800858 528101306 105800793 528101727 105800712 528103238 105800425 528104747 105800149 528105868 105799944 528107064 105799731 528108575 105799463 528110431 105799134 528111385 105798965 528112...

output:

397560103.4816339959216
343764949.5169260489056
314995685.8040496387985
470388562.8405219374399
369514676.7580897980952

result:

ok 5 numbers

Test #34:

score: 0
Accepted
time: 112ms
memory: 5632kb

input:

5
10000 -501317113 815908190
3000 693478209 681557167 693478416 681557435 693479605 681558977 693480659 681560347 693481636 681561619 693481947 681562025 693482896 681563268 693484271 681565098 693485322 681566509 693486379 681567938 693487204 681569054 693488476 681570775 693489313 681571908 693490...

output:

1239559910.4460964073660
62025115.0076963710380
621348456.9660612922162
278611566.9257934704656
934652762.2096404506592

result:

ok 5 numbers

Test #35:

score: 0
Accepted
time: 192ms
memory: 7420kb

input:

5
10000 -700327508 702989707
3000 -254692935 -831597680 -254694172 -831597571 -254696030 -831597409 -254697316 -831597299 -254699111 -831597155 -254700632 -831597034 -254702548 -831596882 -254703508 -831596808 -254705371 -831596670 -254706070 -831596619 -254707817 -831596493 -254708500 -831596446 -2...

output:

240317371.9617961121548
417228210.0622807187028
145169437.6341325243557
154695358.7931913888897
661574446.5657238327549

result:

ok 5 numbers

Test #36:

score: 0
Accepted
time: 190ms
memory: 7656kb

input:

5
10000 -535756158 936247062
3000 166383130 232330358 166382163 232330545 166381842 232330607 166381505 232330671 166380376 232330885 166379421 232331055 166377849 232331322 166376034 232331630 166374935 232331812 166373259 232332089 166371346 232332404 166370470 232332548 166369905 232332639 166369...

output:

321848681.5415453692840
47132901.3201733424612
1221805373.4528377464740
1344708697.9600759472232
7305558.3949492397705

result:

ok 5 numbers

Test #37:

score: 0
Accepted
time: 165ms
memory: 35644kb

input:

2
10000 -758768479 517152843
3000 -196475875 -622544724 -196474245 -622545180 -196474129 -622545212 -196472878 -622545555 -196470969 -622546070 -196470160 -622546279 -196468698 -622546651 -196468113 -622546798 -196466578 -622547183 -196465475 -622547454 -196464203 -622547765 -196462700 -622548130 -1...

output:

253995254.6316990676714
1328238926.0000000000000

result:

ok 2 numbers

Test #38:

score: 0
Accepted
time: 172ms
memory: 35664kb

input:

2
10000 -573977895 641919861
3000 347121719 404913819 347122089 404915132 347122631 404917094 347122901 404918076 347123072 404918705 347123279 404919476 347123792 404921397 347124043 404922339 347124204 404922955 347124654 404924689 347125025 404926127 347125471 404927873 347125713 404928830 347126...

output:

173821476.8911484050623
1528471752.0000000000000

result:

ok 2 numbers

Test #39:

score: 0
Accepted
time: 116ms
memory: 35244kb

input:

1
648 -899534410 747361962
3000 211927638 493123207 211929268 493123656 211930155 493123901 211930800 493124086 211932237 493124502 211933656 493124916 211935226 493125375 211937118 493125929 211939099 493126531 211940702 493127019 211941925 493127397 211943096 493127759 211944029 493128048 21194475...

output:

1309979658.9462507965509

result:

ok found '1309979658.946250916', expected '1309979658.946250916', error '0.000000000'

Test #40:

score: 0
Accepted
time: 124ms
memory: 35272kb

input:

1
657 -611575720 891439134
3000 491719655 -542798612 491719658 -542799409 491719666 -542801221 491719679 -542802627 491719693 -542804004 491719721 -542805714 491719761 -542807477 491719782 -542808319 491719830 -542809996 491719886 -542811761 491719897 -542812096 491719958 -542813875 491719996 -54281...

output:

1432477725.3565021074610

result:

ok found '1432477725.356502056', expected '1432477725.356502056', error '0.000000000'

Test #41:

score: 0
Accepted
time: 209ms
memory: 11004kb

input:

5
10000 -856871457 916406527
100000 623227399 -926813077 623226044 -926814196 623225217 -926814879 623223907 -926815961 623223067 -926816655 623221482 -926817965 623220871 -926818470 623220092 -926819114 623218435 -926820484 623218013 -926820833 623216069 -926822441 623214200 -926823987 623212464 -9...

output:

-1
-1
-1
-1
-1

result:

ok 5 numbers

Test #42:

score: 0
Accepted
time: 195ms
memory: 11272kb

input:

5
10000 -699668634 624085557
100000 506101157 -445281877 506099344 -445280103 506097486 -445278285 506096559 -445277378 506096281 -445277106 506094668 -445275528 506094484 -445275348 506093473 -445274359 506092374 -445273284 506091779 -445272702 506090503 -445271454 506089547 -445270519 506088365 -4...

output:

-1
-1
220429319.2044120460196
-1
353925892.9909762746829

result:

ok 5 numbers

Test #43:

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

input:

5
10000 -622037374 817682512
100000 -625558743 -704636222 -625558729 -704635708 -625558689 -704634239 -625558645 -704632623 -625558596 -704630818 -625558559 -704629455 -625558512 -704627718 -625558462 -704625869 -625558419 -704624273 -625558408 -704623864 -625558394 -704623343 -625558347 -704621591 ...

output:

-1
-1
-1
-1
-1

result:

ok 5 numbers

Test #44:

score: 0
Accepted
time: 306ms
memory: 13068kb

input:

5
10000 -644173104 652456201
100000 541445295 171993628 541445566 171995010 541445715 171995770 541445953 171996985 541445972 171997082 541446355 171999041 541446730 172000960 541447072 172002712 541447310 172003932 541447682 172005839 541448025 172007598 541448409 172009568 541448554 172010312 5414...

output:

-1
-1
-1
-1
218592599.1123368537956

result:

ok 5 numbers

Test #45:

score: 0
Accepted
time: 189ms
memory: 35244kb

input:

1
9046 -641166309 543165538
100000 -951104070 580563380 -951104422 580563946 -951105279 580565324 -951106332 580567017 -951107420 580568766 -951108596 580570656 -951109784 580572565 -951110770 580574149 -951111357 580575092 -951111743 580575712 -951112233 580576499 -951112464 580576870 -951113492 58...

output:

-1

result:

ok found '-1.000000000', expected '-1.000000000', error '-0.000000000'

Test #46:

score: 0
Accepted
time: 198ms
memory: 35276kb

input:

1
9045 -740410642 652751190
100000 419533646 402821427 419534234 402821769 419536223 402822926 419538064 402823997 419540039 402825146 419541895 402826226 419543842 402827359 419545349 402828236 419546581 402828953 419548227 402829911 419548818 402830255 419550371 402831159 419551522 402831829 41955...

output:

-1

result:

ok found '-1.000000000', expected '-1.000000000', error '-0.000000000'

Test #47:

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

input:

1
18 -948940253 629185104
100000 -833855325 174303631 -833856017 174302309 -833856901 174300620 -833857808 174298887 -833858536 174297496 -833859435 174295778 -833860349 174294031 -833861196 174292412 -833861887 174291091 -833862420 174290072 -833863407 174288185 -833864012 174287028 -833864551 1742...

output:

1389928213.8150168540888

result:

ok found '1389928213.815016747', expected '1389928213.815016747', error '0.000000000'

Test #48:

score: 0
Accepted
time: 111ms
memory: 34920kb

input:

1
20 -934151185 527681557
100000 29124091 329049242 29124404 329047347 29124592 329046209 29124842 329044697 29125093 329043179 29125387 329041401 29125495 329040748 29125759 329039152 29126077 329037230 29126401 329035272 29126545 329034402 29126703 329033448 29126783 329032965 29127027 329031492 2...

output:

1461832742.0000000000000

result:

ok found '1461832742.000000000', expected '1461832742.000000000', error '0.000000000'

Extra Test:

score: 0
Extra Test Passed