QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#387913#3524. Long-Exposure Photography1binAC ✓955ms141416kbC++173.1kb2024-04-13 01:12:072024-04-13 01:12:07

Judging History

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

  • [2024-04-13 01:12:07]
  • 评测
  • 测评结果:AC
  • 用时:955ms
  • 内存:141416kb
  • [2024-04-13 01:12:07]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
typedef long double ld;
const int NMAX = 1005;
const int b = 1 << 18;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {1, 0, -1, -1, -1, 0, 1, 1};
int ddx[4] = {0, 1, 0, 1};
int ddy[4] = {0, 0, 1, 1};
set<pair<int, int>> B;
int n, x[NMAX], y[NMAX], w[NMAX], h[NMAX];
ll Black, Gray, mn, mx;
vector<pair<int, int>> W;
vector<pair<ll, ll>> arr, V;
vector<ll> tmp;
int seg[b * 2];

void upd(int ix, int v){
	ix += b;
	while(ix){
		seg[ix] += v;
		ix >>= 1;
	}
	return;
}

int sum(int l, int r){
	l += b; r += b;
	int ret = 0;
	while(l <= r){
		if(l & 1) ret += seg[l++];
		if(!(r & 1)) ret += seg[r--];
		l >>= 1; r >>= 1;
	}
	return ret;
}

void calc(ll i, ll j){
	mn = 6e18; mx = -6e18;
	for(int k = 0; k < 4; k++){
		ll y = i + ddy[k];
		ll x = j + ddx[k];
		mx = max(mx, y * y + x * x);
		mn = min(mn, y * y + x * x);
	}
	arr.emplace_back(mn, mx);
	return;
}

int main(void){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cout << fixed; cout.precision(10);
	cin >> n;
	for(int j = 0; j < n; j++){
		cin >> x[j] >> y[j] >> w[j] >> h[j];
		for(int i = y[j]; i < y[j] + h[j]; i++){
			B.emplace(i, x[j]);
			B.emplace(i, x[j] + w[j] - 1);
		}
		for(int i = x[j]; i < x[j] + w[j]; i++){
			B.emplace(y[j], i);
			B.emplace(y[j] + h[j] - 1, i);
		}
	}
	for(auto& [y, x] : B) {
		calc(y, x);
		for(int k = 0; k < 8; k++){
			int ny = y + dy[k];
			int nx = x + dx[k];
			if(B.find({ny, nx}) == B.end()) W.emplace_back(nx, ny);
		}
	}
	sort(all(arr));
	swap(arr, V);
	
	sort(all(W));
	W.erase(unique(all(W)), W.end());
	for(auto& [x, y] : W) tmp.emplace_back(y);
	sort(all(tmp));
	tmp.erase(unique(all(tmp)),tmp.end());
	assert(tmp.size() <= b);

	vector<tuple<int, int, int>> P;
	for(int i = 0; i < n; i++) {
		int d = lower_bound(all(tmp), y[i]) - tmp.begin();
		int u = lower_bound(all(tmp), y[i] + h[i]) - tmp.begin();
		if(d == u) continue;

		assert(u < tmp.size());
		P.emplace_back(x[i], d, 1);
		P.emplace_back(x[i], u, -1);
		P.emplace_back(x[i] + w[i], d, -1);
		P.emplace_back(x[i] + w[i], u, 1);
	}

	sort(all(P));
	int ix = 0;
	for(auto&[x, y] : W){
		int Y = lower_bound(all(tmp), y) - tmp.begin();
		while(ix < P.size()){
			auto&[xx, yy, v] = P[ix];
			if(xx > x) break;
			upd(yy, v);
			ix++;
		}
		if(!sum(0, Y)) calc(y, x);
	}

	sort(all(arr));
	ll e = 0, ee = 0;
	ix = 0;
	for(auto& [l, r] : V){
		if(r <= e) continue;
		l = max(l, e);
		Gray += r - l;
		while(ix < arr.size() && arr[ix].first <= l) ee = max(ee, arr[ix++].second);
		ee = max(ee, l);
		while(ix < arr.size() && arr[ix].first <= r){
			auto&[ll, rr] = arr[ix++];
			if(ee < ll) Black += ll - ee;
			ee = max(ee, rr);
		}
		if(!ix) Black += r - e, Gray += l - e;
		else if(ee < r) Black += r - ee;
		e = r;
	}
	cout << Black * acos(-1) << '\n';
	cout << (Gray - Black) * acos(-1) << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1000
1000000000 1000000000 1 1
999999998 999999998 1 1
999999996 999999996 1 1
999999994 999999994 1 1
999999992 999999992 1 1
999999990 999999990 1 1
999999988 999999988 1 1
999999986 999999986 1 1
999999984 999999984 1 1
999999982 999999982 1 1
999999980 999999980 1 1
999999978 999999978 1 1
99999...

output:

0.0000000000
12566358066838.1132812500

result:

ok 2 numbers

Test #2:

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

input:

4
-2 1 4 1
-2 -2 1 4
-2 -2 4 1
1 -2 1 4

output:

6.2831853072
15.7079632679

result:

ok 2 numbers

Test #3:

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

input:

1
0 0 2 2

output:

0.0000000000
25.1327412287

result:

ok 2 numbers

Test #4:

score: 0
Accepted
time: 884ms
memory: 135984kb

input:

974
130649494 -334750603 196 194
-128170905 -36925719 192 200
-132188877 -838421900 197 199
-924302066 -208068239 200 192
-225351116 243189063 199 194
698873304 -626471883 192 196
513135835 567427812 199 192
847094373 -611348774 197 200
53900623 859007172 196 199
-325402195 -224151744 191 199
-62573...

output:

0.0000000000
1250051591583879.2500000000

result:

ok 2 numbers

Test #5:

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

input:

1000
1000000000 1000000000 105 146
1000000000 1000000000 65 191
1000000000 1000000000 93 170
1000000000 1000000000 70 95
1000000000 1000000000 189 168
1000000000 1000000000 81 75
1000000000 1000000000 100 58
1000000000 1000000000 194 136
1000000000 1000000000 70 159
1000000000 1000000000 172 61
1000...

output:

0.0000000000
2481858441458.7031250000

result:

ok 2 numbers

Test #6:

score: 0
Accepted
time: 493ms
memory: 67236kb

input:

919
24459 -17003 182 97
21940 -19059 151 82
23909 24347 10 145
-16121 21107 146 60
24751 20741 174 170
23555 24691 158 5
21354 -18085 64 126
-16796 -16960 174 29
21720 -17748 49 16
-20045 23081 41 162
23533 22197 67 156
24758 -17185 121 14
-16613 -17120 58 22
24049 -16091 190 55
22393 -17239 29 96
-...

output:

0.0000000000
2513712513.2770872116

result:

ok 2 numbers

Test #7:

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

input:

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

output:

1897.5219627682
125176.7592822853

result:

ok 2 numbers

Test #8:

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

input:

1000
0 0 1 1
0 -1 1 1
-1 0 1 1
-1 -1 1 1
0 1 1 1
0 -2 1 1
-1 1 1 1
-1 -2 1 1
1 0 1 1
1 -1 1 1
-2 0 1 1
-2 -1 1 1
1 1 1 1
1 -2 1 1
-2 1 1 1
-2 -2 1 1
0 2 1 1
0 -3 1 1
-1 2 1 1
-1 -3 1 1
2 0 1 1
2 -1 1 1
-3 0 1 1
-3 -1 1 1
1 2 1 1
1 -3 1 1
-2 2 1 1
-2 -3 1 1
2 1 1 1
2 -2 1 1
-3 1 1 1
-3 -2 1 1
2 2 1 1...

output:

920.4866475018
147.6548547187

result:

ok 2 numbers

Test #9:

score: 0
Accepted
time: 955ms
memory: 141416kb

input:

1000
1000000000 1000000000 200 200
999999799 -999999999 200 200
-999999798 -999999798 200 200
-999999597 999999397 200 200
999999196 999999196 200 200
999998995 -999999195 200 200
-999998994 -999998994 200 200
-999998793 999998593 200 200
999998392 999998392 200 200
999998191 -999998391 200 200
-999...

output:

0.0000000000
2513022042733947.5000000000

result:

ok 2 numbers

Test #10:

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

input:

999
-999999999 4 1 2
-999999997 3 1 1
-999999995 4 1 1
-999999993 2 1 3
-999999991 5 1 2
-999999989 3 1 3
-999999987 1 1 5
-999999985 4 1 2
-999999983 1 1 2
-999999981 3 1 2
-999999979 2 1 4
-999999977 3 1 5
-999999975 3 1 1
-999999973 3 1 4
-999999971 3 1 1
-999999969 5 1 3
-999999967 3 1 4
-999999...

output:

0.0000000000
6276895939598.1972656250

result:

ok 2 numbers

Test #11:

score: 0
Accepted
time: 398ms
memory: 32084kb

input:

1000
0 0 200 200
1 1 200 200
2 2 200 200
3 3 200 200
4 4 200 200
5 5 200 200
6 6 200 200
7 7 200 200
8 8 200 200
9 9 200 200
10 10 200 200
11 11 200 200
12 12 200 200
13 13 200 200
14 14 200 200
15 15 200 200
16 16 200 200
17 17 200 200
18 18 200 200
19 19 200 200
20 20 200 200
21 21 200 200
22 22 2...

output:

0.0000000000
9032713.4807866812

result:

ok 2 numbers

Test #12:

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

input:

1
-2 1 4 1

output:

0.0000000000
21.9911485751

result:

ok 2 numbers

Test #13:

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

input:

2
-2 -2 1 4
1 -2 1 4

output:

0.0000000000
21.9911485751

result:

ok 2 numbers

Test #14:

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

input:

2
-2 -2 1 4
-2 -2 4 1

output:

0.0000000000
21.9911485751

result:

ok 2 numbers

Test #15:

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

input:

3
-2 1 4 1
-2 -2 4 1
1 -2 1 4

output:

0.0000000000
21.9911485751

result:

ok 2 numbers

Test #16:

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

input:

5
-1 -1 2 2
-3 2 6 1
-3 -3 1 6
-3 -3 6 1
2 -3 1 6

output:

6.2831853072
43.9822971503

result:

ok 2 numbers

Test #17:

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

input:

16
-2 -2 1 1
-2 -1 1 1
-2 0 1 1
-2 1 1 1
-1 -2 1 1
-1 -1 1 1
-1 0 1 1
-1 1 1 1
0 -2 1 1
0 -1 1 1
0 0 1 1
0 1 1 1
1 -2 1 1
1 -1 1 1
1 0 1 1
1 1 1 1

output:

12.5663706144
12.5663706144

result:

ok 2 numbers

Test #18:

score: 0
Accepted
time: 442ms
memory: 71284kb

input:

1000
45618677 863967299 100 72
-978038675 105564443 187 98
291851600 -881147847 116 122
641615331 751255526 66 121
-537207822 691535746 171 137
-71119496 -885367037 189 105
-965587251 -438712116 162 193
-922855743 -844506770 14 135
-980539471 662463112 7 56
-379456093 575147744 154 109
693999897 937...

output:

0.0000000000
639780673355738.2500000000

result:

ok 2 numbers

Test #19:

score: 0
Accepted
time: 455ms
memory: 72656kb

input:

1000
-242452104 695630744 43 150
-950731690 -466841907 183 22
980174777 403165313 48 182
464612196 -176328953 56 95
967846100 239125398 66 198
147866705 904405038 98 63
-396534060 -414049753 135 138
-641739945 -992739118 154 153
555407980 621568947 102 44
-992756607 -73450965 18 171
-817769300 -8554...

output:

0.0000000000
654096425727962.3750000000

result:

ok 2 numbers

Test #20:

score: 0
Accepted
time: 455ms
memory: 72444kb

input:

1000
-555545085 502197874 166 8
899516530 -5205347 21 79
547895242 568662052 57 164
-840873342 994372689 38 16
-806950991 -289634860 47 100
-796530355 449577280 132 126
-870860602 -490211606 165 64
591742749 -506923491 41 65
995274383 -695900443 24 67
298894210 -935983005 97 5
632679047 67169953 120...

output:

0.0000000000
676895631184301.0000000000

result:

ok 2 numbers

Test #21:

score: 0
Accepted
time: 447ms
memory: 70768kb

input:

1000
215069295 311962008 79 126
753820418 -605997623 76 72
-945595253 -320837693 24 174
-902357473 -899635828 145 182
-422351680 -801705162 72 69
424885268 -892371657 156 182
-520161438 -539542772 113 124
-287492712 151291766 158 184
-684229873 -866072412 61 146
-472070035 421414335 170 113
-8994233...

output:

0.0000000000
658585529932309.7500000000

result:

ok 2 numbers

Test #22:

score: 0
Accepted
time: 855ms
memory: 134376kb

input:

961
-54725486 -752784206 199 194
-720987145 -331778171 194 198
54489464 -816765222 200 198
-811686626 -216087432 195 198
-720342333 668983087 191 193
292320448 -188262820 195 199
-601438488 -966968582 197 191
463763437 738239708 191 194
985455503 376747050 198 191
-955031122 -298399148 198 197
-1151...

output:

0.0000000000
1267109050238817.2500000000

result:

ok 2 numbers

Test #23:

score: 0
Accepted
time: 887ms
memory: 137868kb

input:

991
-266815619 941561279 192 195
-281651976 -665359568 196 200
194140051 -839144874 200 193
-751364506 781242451 194 198
851662848 -62618192 195 198
858444873 -912764991 197 194
-749002536 294367925 197 194
-72816831 837790211 196 191
631867843 -291922523 198 200
42717909 -621272506 191 193
-4604173...

output:

0.0000000000
1311161201843117.7500000000

result:

ok 2 numbers

Test #24:

score: 0
Accepted
time: 915ms
memory: 137068kb

input:

984
-434535548 -536470249 193 194
215838388 -938079593 191 200
406570506 -786305422 195 191
-601284850 802802596 196 197
392724706 -669899895 192 191
499363869 -410731141 199 191
359708262 825619200 195 194
697760723 116455952 199 199
579985703 -649052528 192 194
-587132121 523324801 196 197
7370193...

output:

0.0000000000
1271912905501672.7500000000

result:

ok 2 numbers

Test #25:

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

input:

987
1000000000 1000000000 45 14
1000000000 1000000000 18 173
1000000000 1000000000 100 24
1000000000 1000000000 128 64
1000000000 1000000000 184 89
1000000000 1000000000 70 26
1000000000 1000000000 120 112
1000000000 1000000000 189 163
1000000000 1000000000 190 105
1000000000 1000000000 102 174
1000...

output:

0.0000000000
2481858441421.0043945312

result:

ok 2 numbers

Test #26:

score: 0
Accepted
time: 235ms
memory: 24572kb

input:

826
-11 -93 80 148
195 209 154 112
-249 -123 180 166
232 -174 9 179
32 -73 107 24
103 -189 84 149
58 -217 200 151
-154 -72 137 18
66 86 196 168
228 11 142 102
116 81 8 121
-100 -50 78 168
240 34 46 136
234 -55 130 81
-220 -106 23 81
-153 229 16 159
-25 15 28 163
113 -195 187 121
190 -169 83 147
-137...

output:

182997.7720716055
733181.7519021323

result:

ok 2 numbers

Test #27:

score: 0
Accepted
time: 230ms
memory: 25160kb

input:

859
105 120 77 48
137 -152 173 153
-4 47 123 102
-128 -52 171 64
151 0 45 84
181 -235 49 60
89 141 15 6
-246 -210 112 14
-138 -38 163 140
-7 102 50 135
137 239 40 124
236 -241 113 10
-58 -10 8 157
218 225 168 56
-237 57 149 182
196 -233 182 12
100 -191 12 144
79 -157 135 13
85 -33 79 174
-168 -76 11...

output:

163340.8268380941
813267.2318274433

result:

ok 2 numbers

Test #28:

score: 0
Accepted
time: 424ms
memory: 60604kb

input:

814
24102 22548 16 88
-20448 23645 178 165
24426 21365 26 10
24603 -17601 48 189
20622 24755 92 139
25005 -17618 44 87
-17209 -20086 103 158
21547 -17422 44 112
24760 21291 154 55
-16696 22432 122 141
-19372 -18052 187 174
-19432 -15837 103 77
-17184 -16869 142 155
24471 -16287 125 171
22815 -20154 ...

output:

0.0000000000
2450067832.7964353561

result:

ok 2 numbers

Test #29:

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

input:

5
0 -2 1 6
-2 -1 5 1
-2 -1 1 4
-2 2 5 1
2 -1 1 4

output:

0.0000000000
56.5486677646

result:

ok 2 numbers

Test #30:

score: 0
Accepted
time: 201ms
memory: 19504kb

input:

979
21 -999999914 152 149
500000087 500000042 168 138
500000035 500000084 108 200
85 55 70 3
500000020 500000018 96 164
500000051 500000079 174 86
500000011 500000015 164 95
57 -999999901 138 103
500000021 500000099 99 113
500000005 500000036 191 167
-999999991 -999999965 151 196
82 36 74 160
-99999...

output:

0.0000000000
6408849298796.5605468750

result:

ok 2 numbers

Test #31:

score: 0
Accepted
time: 184ms
memory: 19004kb

input:

951
74 -999999966 103 185
55 19 67 40
500000083 500000044 12 20
-999999964 -999999999 74 184
500000058 500000074 103 143
500000094 500000033 16 20
1 5 90 124
8 7 99 12
95 -999999972 101 10
53 -999999983 153 43
26 -999999904 191 138
76 70 42 75
-999999953 -999999929 47 45
53 0 165 50
44 75 138 148
6 ...

output:

0.0000000000
6952344816724.3662109375

result:

ok 2 numbers

Test #32:

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

input:

873
-999999971 -999999984 2 174
999999983 -999999937 57 106
999999996 999999900 103 153
-999999905 999999998 9 59
999999963 999999950 169 125
999999939 -999999983 29 28
-999999956 999999938 164 95
-999999974 999999968 174 133
999999974 -999999928 78 32
999999975 999999936 96 25
-999999955 -999999940...

output:

0.0000000000
5472654147691.7158203125

result:

ok 2 numbers

Test #33:

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

input:

999
999999968 999999960 194 161
-999999914 -999999948 76 113
999999957 -999999955 83 65
-999999924 -999999918 65 170
-999999902 -999999922 13 123
-999999975 -999999943 82 154
999999941 -999999907 54 60
-999999943 -999999974 192 74
999999988 999999967 185 142
999999966 -999999984 139 200
999999968 -9...

output:

0.0000000000
5340707203590.9931640625

result:

ok 2 numbers

Test #34:

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

input:

4
100 -100 200 200
-100 -300 200 200
-300 -100 200 200
-100 100 200 200

output:

0.0000000000
282743.3388230814

result:

ok 2 numbers

Test #35:

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

input:

4
50 -100 200 200
-100 -250 200 200
-250 -100 200 200
-100 50 200 200

output:

47123.8898038469
172787.5959474386

result:

ok 2 numbers

Test #36:

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

input:

4
0 -100 200 200
-100 -200 200 200
-200 -100 200 200
-100 0 200 200

output:

62831.8530717959
94247.7796076938

result:

ok 2 numbers

Test #37:

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

input:

1
-1 -1 200 200

output:

3.1415926536
248817.2797569652

result:

ok 2 numbers

Test #38:

score: 0
Accepted
time: 759ms
memory: 91224kb

input:

1000
0 0 172 200
0 200 31 200
0 400 122 200
0 600 53 200
0 800 155 200
0 1000 35 200
0 1200 73 200
0 1400 83 200
0 1600 100 200
0 1800 99 200
0 2000 40 200
0 2200 171 200
0 2400 155 200
0 2600 167 200
0 2800 186 200
0 3000 114 200
0 3200 8 200
0 3400 170 200
0 3600 148 200
0 3800 40 200
0 4000 58 20...

output:

0.0000000000
101787707185.1056671143

result:

ok 2 numbers

Test #39:

score: 0
Accepted
time: 731ms
memory: 90148kb

input:

1000
0 0 159 200
0 200 76 200
0 400 181 200
0 600 112 200
0 800 95 200
0 1000 153 200
0 1200 149 200
0 1400 60 200
0 1600 29 200
0 1800 187 200
0 2000 58 200
0 2200 133 200
0 2400 54 200
0 2600 6 200
0 2800 147 200
0 3000 193 200
0 3200 21 200
0 3400 83 200
0 3600 174 200
0 3800 118 200
0 4000 2 200...

output:

0.0000000000
101787601988.8756713867

result:

ok 2 numbers

Test #40:

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

input:

10
-1 -10 2 8
-3 -8 6 2
-2 -4 4 2
-3 -3 2 2
1 -3 2 2
-4 -2 2 4
2 -2 2 4
-3 1 2 2
1 1 2 2
-2 2 4 2

output:

25.1327412287
285.8849314767

result:

ok 2 numbers

Test #41:

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

input:

777
16 -60 49 18
59 34 42 114
-15 62 19 91
61 -3 1 8
-42 -46 13 17
43 -43 194 15
61 29 82 38
60 -2 185 16
36 -53 25 6
59 -23 31 19
-20 58 9 175
61 23 162 23
62 30 111 33
27 54 8 60
46 -39 50 14
61 28 1 67
66 -19 32 4
-63 7 14 38
-18 -59 4 2
-61 -18 16 17
57 26 149 85
-40 -43 16 2
-55 39 7 67
-58 -18...

output:

741.4158662472
361323.9958673229

result:

ok 2 numbers

Test #42:

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

input:

897
-95 -50 35 27
-106 -16 32 16
96 -46 56 4
-119 34 30 159
-118 -38 32 15
83 95 8 116
-59 92 6 164
-100 3 17 200
-66 106 29 45
-57 85 8 31
61 78 129 5
-90 54 33 185
-62 -89 21 35
35 -108 67 17
-101 -49 32 35
114 -48 157 28
28 98 79 76
30 113 59 1
-128 4 20 169
127 -4 153 25
-28 112 24 31
101 7 10 3...

output:

6707.3003154142
449376.5547621376

result:

ok 2 numbers

Test #43:

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

input:

21
-1 -1 2 2
-4 -4 2 2
-4 -2 2 2
-4 0 2 2
-4 2 2 2
-2 2 2 2
0 2 2 2
2 2 2 2
2 0 2 2
2 -2 2 2
2 -4 2 2
0 -4 2 2
-2 -4 2 2
5 5 1 1
5 -5 200 10
5 -6 1 1
-5 -205 10 200
-6 -6 1 1
-205 -5 200 10
-6 5 1 1
-5 5 10 200

output:

62.8318530718
132034.8560450718

result:

ok 2 numbers

Test #44:

score: 0
Accepted
time: 582ms
memory: 78300kb

input:

794
-1 -100 2 200
2 -100 3 200
6 -100 4 200
11 -100 5 200
17 -100 6 200
24 -100 7 200
32 -100 8 200
41 -100 9 200
51 -100 10 200
62 -100 11 200
74 -100 12 200
87 -100 13 200
101 -100 14 200
116 -100 15 200
132 -100 16 200
149 -100 17 200
167 -100 18 200
186 -100 19 200
206 -100 20 200
227 -100 21 20...

output:

12921.3705842148
1289846560.9168615341

result:

ok 2 numbers

Test #45:

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

input:

3
-80 -80 160 160
-100 -40 200 80
-40 -100 80 200

output:

25132.7412287183
15079.6447372310

result:

ok 2 numbers

Test #46:

score: 0
Accepted
time: 35ms
memory: 6896kb

input:

1000
0 0 10 10
0 -10 10 10
-10 0 10 10
-10 -10 10 10
0 10 10 10
0 -20 10 10
-10 10 10 10
-10 -20 10 10
10 0 10 10
10 -10 10 10
-20 0 10 10
-20 -10 10 10
10 10 10 10
10 -20 10 10
-20 10 10 10
-20 -20 10 10
0 20 10 10
0 -30 10 10
-10 20 10 10
-10 -30 10 10
20 0 10 10
20 -10 10 10
-30 0 10 10
-30 -10 1...

output:

92048.6647501809
14765.4854718720

result:

ok 2 numbers

Test #47:

score: 0
Accepted
time: 814ms
memory: 86852kb

input:

1000
0 0 200 200
0 -200 200 200
-200 0 200 200
-200 -200 200 200
0 200 200 200
0 -400 200 200
-200 200 200 200
-200 -400 200 200
200 0 200 200
200 -200 200 200
-400 0 200 200
-400 -200 200 200
200 200 200 200
200 -400 200 200
-400 200 200 200
-400 -400 200 200
0 400 200 200
0 -600 200 200
-200 400 2...

output:

36819465.9000723734
5906194.1887488114

result:

ok 2 numbers

Test #48:

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

input:

1000
-557048988 -92716759 2 1
-352199465 854614940 2 3
-317400283 643643143 3 4
-824610108 633529762 1 1
-891686133 596161259 3 1
232315727 113801033 2 1
709672141 350496504 2 4
962112916 781548307 2 1
-537151576 -742419720 1 3
961870665 110648960 2 2
40001951 -503013266 4 4
-980788400 215391843 2 4...

output:

0.0000000000
16650149192996.9707031250

result:

ok 2 numbers

Test #49:

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

input:

1000
-702156200 595448794 2 4
298643236 -662946583 2 2
545012587 984800351 4 2
635337291 547146615 2 1
-895698723 940091980 1 1
-350442589 896509381 2 4
906079324 766587059 2 1
-721077555 -399270752 2 3
-250875081 -423233755 3 3
-719612355 -952231844 3 1
39262649 825400232 4 2
-392178772 -472883708 ...

output:

0.0000000000
16631349746282.5039062500

result:

ok 2 numbers

Test #50:

score: 0
Accepted
time: 946ms
memory: 141320kb

input:

1000
1000000000 1000000000 200 200
999999800 -1000000000 200 200
-999999800 -999999800 200 200
-999999600 999999400 200 200
999999200 999999200 200 200
999999000 -999999200 200 200
-999999000 -999999000 200 200
-999998800 999998600 200 200
999998400 999998400 200 200
999998200 -999998400 200 200
-99...

output:

0.0000000000
2513023298114372.0000000000

result:

ok 2 numbers

Test #51:

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

input:

996
-125 -12 1 1
-125 -11 1 1
-125 -10 1 1
-125 -9 1 1
-125 -8 1 1
-125 -7 1 1
-125 -6 1 1
-125 -5 1 1
-125 -4 1 1
-125 -3 1 1
-125 -2 1 1
-125 -1 1 1
-125 0 1 1
-125 1 1 1
-125 2 1 1
-125 3 1 1
-125 4 1 1
-125 5 1 1
-125 6 1 1
-125 7 1 1
-125 8 1 1
-125 9 1 1
-125 10 1 1
-125 11 1 1
-124 -20 1 1
-1...

output:

28.2743338823
2151.9909677090

result:

ok 2 numbers

Test #52:

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

input:

996
-250 -24 2 2
-250 -22 2 2
-250 -20 2 2
-250 -18 2 2
-250 -16 2 2
-250 -14 2 2
-250 -12 2 2
-250 -10 2 2
-250 -8 2 2
-250 -6 2 2
-250 -4 2 2
-250 -2 2 2
-250 0 2 2
-250 2 2 2
-250 4 2 2
-250 6 2 2
-250 8 2 2
-250 10 2 2
-250 12 2 2
-250 14 2 2
-250 16 2 2
-250 18 2 2
-250 20 2 2
-250 22 2 2
-248 ...

output:

113.0973355292
8607.9638708360

result:

ok 2 numbers

Test #53:

score: 0
Accepted
time: 879ms
memory: 112828kb

input:

996
-25000 -2400 200 200
-25000 -2200 200 200
-25000 -2000 200 200
-25000 -1800 200 200
-25000 -1600 200 200
-25000 -1400 200 200
-25000 -1200 200 200
-25000 -1000 200 200
-25000 -800 200 200
-25000 -600 200 200
-25000 -400 200 200
-25000 -200 200 200
-25000 0 200 200
-25000 200 200 200
-25000 400 2...

output:

1130973.3552923256
86079638.7083603293

result:

ok 2 numbers

Test #54:

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

input:

10
-1 -1 2 1
-1 -1 1 2
-3 0 1 3
0 -3 3 1
-3 2 6 1
2 -3 1 6
-5 -5 10 1
-5 -5 1 10
4 -5 1 5
-5 4 5 1

output:

0.0000000000
150.7964473723

result:

ok 2 numbers

Test #55:

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

input:

995
-125 -12 1 1
-125 -11 1 1
-125 -10 1 1
-125 -9 1 1
-125 -8 1 1
-125 -7 1 1
-125 -6 1 1
-125 -5 1 1
-125 -4 1 1
-125 -3 1 1
-125 -2 1 1
-125 -1 1 1
-125 0 1 1
-125 1 1 1
-125 2 1 1
-125 3 1 1
-125 4 1 1
-125 5 1 1
-125 6 1 1
-125 7 1 1
-125 8 1 1
-125 9 1 1
-125 10 1 1
-125 11 1 1
-124 -20 1 1
-1...

output:

0.0000000000
2180.2653015913

result:

ok 2 numbers

Test #56:

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

input:

998
0 0 1 1
0 -1 1 1
-1 0 1 1
-1 -1 1 1
0 1 1 1
0 -2 1 1
-1 1 1 1
-1 -2 1 1
1 0 1 1
1 -1 1 1
-2 0 1 1
-2 -1 1 1
1 1 1 1
1 -2 1 1
-2 1 1 1
-2 -2 1 1
0 2 1 1
0 -3 1 1
-1 2 1 1
-1 -3 1 1
2 0 1 1
2 -1 1 1
-3 0 1 1
-3 -1 1 1
1 2 1 1
1 -3 1 1
-2 2 1 1
-2 -3 1 1
2 1 1 1
2 -2 1 1
-3 1 1 1
-3 -2 1 1
2 2 1 1
...

output:

757.1238295151
311.0176727054

result:

ok 2 numbers