QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#191886#6124. King Of Zombiesucup-team1209#AC ✓847ms19828kbC++201.8kb2023-09-30 12:11:222023-09-30 12:11:22

Judging History

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

  • [2023-09-30 12:11:22]
  • 评测
  • 测评结果:AC
  • 用时:847ms
  • 内存:19828kb
  • [2023-09-30 12:11:22]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
const int N = 1005;
using ll = long long;
using u64 = unsigned long long;
using db = double;
using cp = std::complex<db>;
using pr = std::pair<db, db>;
const db inf = 1e30;
const db eps = 1e-9;
int n;

db D;
cp p[N], v[N];
cp get() {
	db x, y; cin >> x >> y;
	return cp(x, y);
}
pr get(int i, int j) {
	cp d = p[i] - p[j], v = ::v[i] - ::v[j];
	db l = 0, r = 1e5;
	auto eval = [&](db t) {
		cp z = d + t * v;
		return z.real() * z.real() + z.imag() * z.imag();
	};
	for(int i = 0;i < 120;++i) {
		db ml = (l + l + r) / 3;
		db mr = (l + r + r) / 3;
		if(eval(ml) < eval(mr)) {
			r = mr;
		} else {
			l = ml;
		}
	}
	if(eval(l) > (D + eps) * (D + eps)) {
		return {-1, -1};
	}
	db L = l, R = l, m = 1e5;
	for(int c = 0;c < 80;++c) {
		m /= 2;
		if(eval((L - m)) <= D * D) L -= m;
		if(eval((R + m)) <= D * D) R += m;
	}
	return {L, R};
}
pr edge[N][N];

db T[N];
using pd = std::pair<db, int>;
std::priority_queue<pd, std::vector<pd>, std::greater<pd>> Q;
void relax(int s, db d) {
	if(T[s] > d) {
		T[s] = d;
		Q.emplace(d, s);
	}
}
int vis[N];
void dijk(int s) {
	for(int i = 0;i <= n;++i) T[i] = inf;
	relax(0, 0);
	for(;Q.size();) {
		int i = Q.top().second; Q.pop();
		if(vis[i]) continue;
		vis[i] = 1;
		for(int j = 0;j <= n;++j) if(i != j) {
			if(T[i] > edge[i][j].second) continue;
			relax(j, std::max(T[i], edge[i][j].first));
		}
	}
}
int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);

	cin >> n >> D;
	for(int i = 0;i <= n;++i) {
		p[i] = get();
		v[i] = get();
	}
	for(int i = 0;i <= n;++i) {
		for(int j = i + 1;j <= n;++j) {
			edge[i][j] = edge[j][i] = get(i, j);
		}
	}
	dijk(0);
	for(int i = 1;i <= n;++i) {
		if(T[i] > 1e20) {
			puts("-1");
		} else {
			printf("%.10lf\n", T[i]);
		}
	}
}

详细

Test #1:

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

input:

5 3
0 0 3 0
10 10 0 -3
1 1 -1 -1
16 1 -1 0
100 100 100 100
-100 -3 10 0

output:

2.6262265521
0.0000000000
3.0000000000
-1
14.2857142815

result:

ok 5 numbers

Test #2:

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

input:

4 10
0 0 0 0
10 0 0 0
20 0 0 0
30 0 0 0
41 0 0 0

output:

0.0000000000
0.0000000000
0.0000000000
-1

result:

ok 4 numbers

Test #3:

score: 0
Accepted
time: 507ms
memory: 17520kb

input:

814 5261
8674 -10000 83 9959
-3135 4963 -5450 -980
-6718 -5021 -5412 1206
8906 -9471 -4357 5471
-3795 2180 -4645 -2664
9110 -5528 9221 -3130
-3916 1465 -6825 5446
1767 -3479 -6871 -7960
-3523 5303 -1141 7806
3362 -3357 7529 -6106
-7323 -8776 3458 3288
-4825 -5940 -4857 95
-3169 6767 -3056 -2340
3228...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 814 numbers

Test #4:

score: 0
Accepted
time: 145ms
memory: 11616kb

input:

470 235
5883 -1751 1075 368
7790 2418 3758 -3846
-5164 -3433 -5837 -7492
-3987 -6763 6899 -9252
-7032 2446 -4829 6204
5952 -1391 -6466 -1366
1902 -976 -6563 3105
-726 2931 4726 5388
5891 -2901 -3071 906
1237 6576 -2018 1582
-4444 -974 -537 -7998
-5090 -3067 -6005 -6746
7139 -9713 -6108 5218
150 -569...

output:

-1
-1
-1
-1
-1
-1
-1
3.8776035416
-1
-1
-1
-1
-1
1.8672340236
9.4843862520
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0.4692992262
1.2760146655
-1
-1
-1
-1
0.8519144711
0.8400612858
-1
-1
-1
2.0495981783
-1
-1
-1
16.6338579748
1.1308375470
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 470 numbers

Test #5:

score: 0
Accepted
time: 210ms
memory: 12768kb

input:

513 6743
672 -7437 -673 -4800
2473 7996 -6326 3500
5785 -4490 8411 9527
-6418 -4031 -7778 -7792
9650 -8109 -6418 4041
-6638 9373 7042 1792
-2582 601 2410 8495
7222 1876 -8251 1827
-6668 3503 4439 -2064
1004 6600 4235 -5489
-995 77 4672 7871
-2757 -6231 3455 2819
-1903 -7115 -7370 -9396
-9766 -581 -7...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 513 numbers

Test #6:

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

input:

532 1356
592 8158 1209 4121
8684 -404 6292 -1509
-5665 9852 -8564 -4450
-225 -791 -3099 -5575
-3121 8560 5045 6229
-5053 3552 -871 1805
3034 3522 -1398 7523
-6851 -6621 -5539 5163
561 4300 -7900 -6939
64 -7900 4459 -3273
-4009 -5022 -9559 2288
1829 -7181 -4184 3853
5126 4300 2628 1409
5769 -2768 548...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 532 numbers

Test #7:

score: 0
Accepted
time: 267ms
memory: 14648kb

input:

643 343
-6247 451 4007 656
3579 -2469 720 -1888
-2485 4858 -9720 3473
-8864 9702 -2158 5692
-9764 6779 5532 9028
9723 -3172 7666 -3027
-4979 1933 2796 -3016
-6078 -4470 -211 4094
-5796 -7180 -8344 -4196
-1820 1461 8832 -3253
-848 3229 -678 5283
-5949 3456 3712 -4297
9845 7690 9994 -6191
-4871 -2949 ...

output:

1.6834008052
-1
-1
-1
-1
0.7878161749
0.5525516670
-1
-1
-1
0.3979023562
-1
2.4381826347
1.4890329428
7.6708666801
3.0161985433
-1
-1
-1
7.5952025662
-1
3.4768956438
-1
1.1149233424
1.2285466413
-1
0.7457215032
-1
-1
-1
-1
-1
4.0849610680
1.3055001709
-1
-1
-1
0.7014740416
3.2241012365
-1
-1
-1
-1
4...

result:

ok 643 numbers

Test #8:

score: 0
Accepted
time: 299ms
memory: 15892kb

input:

649 3052
1634 -9666 -5898 2948
-3830 8114 -1787 -3584
-4100 -5438 8239 -9293
9908 -3521 -633 -3613
-7653 -5639 -7483 6603
1242 2634 2971 598
9456 6152 -1814 6843
-4929 8914 1158 5029
-3091 4248 140 -895
9284 -6769 -9699 -9594
-2824 6832 4073 -8505
4594 3404 -1270 -5966
9563 -1447 -4108 4073
-3025 -2...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 649 numbers

Test #9:

score: 0
Accepted
time: 574ms
memory: 18916kb

input:

870 5514
-1985 -9924 -5613 -9347
3241 -128 -5784 33
-4825 -572 -1340 2283
4080 -3302 5218 4158
-1317 -3620 7471 1536
-1154 6167 3855 8688
-3304 -1866 4963 3167
-8053 3553 3507 7352
5065 3337 319 -5145
7448 -8719 9929 7044
-6110 -612 7888 882
-3818 3492 7954 -6249
-3942 -5128 -8938 5992
3112 -122 79 ...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 870 numbers

Test #10:

score: 0
Accepted
time: 602ms
memory: 19828kb

input:

886 5788
4869 805 -1826 8306
2185 3157 -4632 7777
5595 -5345 6978 -9690
2367 3972 -9402 726
5510 -8129 -1422 -4013
4131 7664 -8198 -2791
9043 -2491 8462 -1914
-6524 4703 4495 -8856
5351 -7212 2052 -3286
-2623 6477 8934 -1888
9084 1877 -625 -9152
7860 -5086 -4514 7105
-4796 -7466 -8809 -52
7692 6702 ...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 886 numbers

Test #11:

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

input:

314 5962
2258 -8497 -2386 5236
-428 6368 5126 9422
-3688 -8063 -4141 -4815
-853 199 -2565 -3687
534 -5684 2036 -1824
7442 -4207 8410 4896
2641 3361 -8534 9797
-9026 7734 -6819 7914
460 3684 6187 6603
7444 -4285 -3281 1650
7287 -1985 2698 3794
-6447 2709 9001 3869
-6024 2374 8468 -2719
-6641 6761 763...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 314 numbers

Test #12:

score: 0
Accepted
time: 522ms
memory: 18684kb

input:

821 5983
-8357 -5982 567 -3431
27 3101 -1648 1733
-3386 2420 -9294 -3877
-8981 -7706 -1073 5824
-6539 -53 3538 -5322
-9740 6341 9302 -4074
7003 8101 7115 7103
-2801 1876 5693 -6039
6032 -9161 693 -2299
8895 -3560 -7514 1319
-8687 -4261 -906 7503
-9920 -3828 1091 4014
-4722 -723 3200 5898
-917 7491 -...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 821 numbers

Test #13:

score: 0
Accepted
time: 739ms
memory: 19796kb

input:

1000 4747
4970 8674 -10000 83
9959 -3135 4963 -5450
-980 -6718 -5021 -5412
1206 8906 -9471 -4357
5471 -3795 2180 -4645
-2664 9110 -5528 9221
-3130 -3916 1465 -6825
5446 1767 -3479 -6871
-7960 -3523 5303 -1141
7806 3362 -3357 7529
-6106 -7323 -8776 3458
3288 -4825 -5940 -4857
95 -3169 6767 -3056
-234...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #14:

score: 0
Accepted
time: 847ms
memory: 19760kb

input:

1000 8968
-5350 7923 2783 3409
1219 2941 9187 -7428
9803 -8286 3099 -7049
-7487 -1266 3521 9843
-530 237 -6361 5701
-8580 -5161 -9458 -8646
6689 1331 3081 -3533
-4386 -7013 -4636 -5818
-68 -2663 4856 8768
1285 -9886 -8423 -866
7154 -1491 -81 7373
-3102 -3032 2902 5216
-1331 -226 3158 -19
1920 6649 5...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 722ms
memory: 19740kb

input:

1000 3685
-7383 -377 -2723 3029
-2493 -2981 -8929 1564
101 -4088 2025 4793
-6663 8915 8708 4058
-6426 1405 -8811 -9888
437 -7050 -2828 -8785
-8980 -2683 9334 1620
-3768 1498 2041 9569
-953 -4807 -250 -7601
-5737 -1586 5466 639
-62 3533 -9375 1745
1643 -8798 -7217 2473
-7954 -8314 4197 5161
407 -2869...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #16:

score: 0
Accepted
time: 811ms
memory: 19756kb

input:

1000 7779
-83 -6062 6465 -619
3622 -535 -1561 -1436
1194 3524 2198 7756
-2565 -4391 4086 -5079
2187 526 8346 -3379
-9014 -1634 3024 5216
8525 8864 8021 -926
-4295 6866 2809 -6692
8830 -6286 -8592 5530
5988 -2345 8435 -670
428 304 8957 -6518
4010 -1230 4299 -3378
-247 6367 -2639 -3858
-2449 1072 5871...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #17:

score: 0
Accepted
time: 650ms
memory: 19624kb

input:

1000 367
7870 -167 -2515 -6975
2856 -2621 7937 1386
-1908 -3582 1236 6091
-3505 9712 3761 9548
-8143 2480 -8749 3137
1848 4624 -2542 9255
8798 3005 3288 -8920
-3029 -9267 9804 1357
9924 8377 -9639 -4839
-9852 -6986 -4299 2542
-9713 -1865 -6012 5169
-9116 -9545 731 -4041
-7303 -8748 9843 -1061
-5474 ...

output:

0.2723583328
1.0674843236
-1
-1
-1
0.2440444042
0.6398775615
0.6301894201
-1
-1
3.6663455137
1.0181514369
1.0056720038
1.7640881479
1.6733181103
1.1663377790
-1
-1
0.4781567952
4.6910978576
0.3708380357
-1
0.5385462664
7.6530338092
0.3242226586
-1
-1
1.0487461738
11.3644269859
-1
0.2440444042
-1
-1
...

result:

ok 1000 numbers

Test #18:

score: 0
Accepted
time: 798ms
memory: 19548kb

input:

1000 7034
4796 -4472 9218 -4549
-8447 -6070 4486 168
9889 4756 4961 -6819
7730 3619 538 2306
2134 -9296 -9397 -1779
2756 72 -3697 -2728
-8010 3791 -1544 -6409
5577 -5291 -8365 -5618
3114 -9044 3997 8424
-6076 -2538 6710 -8953
-2332 1907 6611 -8185
5142 6983 -957 -6253
-8247 4249 5737 8200
3705 -2355...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #19:

score: 0
Accepted
time: 701ms
memory: 19808kb

input:

1000 3023
653 3503 -8597 7046
7204 -6088 -2291 -5222
-5367 4811 4332 768
9436 3555 -3480 4777
-8209 -1414 -1487 2744
5093 -6803 3023 5993
1357 -2792 -3676 3429
9407 -7077 6722 -8023
-6578 1699 -6241 3434
1519 -3912 -5650 6434
9334 -5579 4875 -4502
-2540 5304 1263 8120
9429 2863 5168 4897
-1830 1559 ...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #20:

score: 0
Accepted
time: 806ms
memory: 19764kb

input:

1000 7257
1012 6701 3271 9093
-1083 -7424 -8075 -6841
-6820 2317 -2694 -6065
791 6786 -6516 -3387
-35 713 4141 -6414
-2609 9656 -4591 799
7198 -7782 9355 6170
-8823 412 -3040 6438
5522 7109 -3607 7935
-7045 596 -4807 6775
-6931 -1513 600 -2114
-1142 5879 -2429 -2857
8513 2683 -6198 -5797
-9347 1129 ...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #21:

score: 0
Accepted
time: 841ms
memory: 19564kb

input:

1000 9114
1476 -4037 -8995 8262
8908 -1487 944 -5516
9596 3650 834 1070
7465 -3222 2414 2288
-2668 -8938 -4207 6003
6021 4793 -8241 -6545
-9553 6783 4946 -2850
-3838 -5766 -1767 -2851
-4477 -4400 -148 -861
1862 -2576 -5312 -9308
-7990 4073 -6799 -1084
204 6189 676 -6653
-322 4373 -5598 1673
3104 -52...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #22:

score: 0
Accepted
time: 681ms
memory: 19828kb

input:

1000 1913
-2750 -6291 96 1178
1797 3051 -8940 -1995
8432 -2557 -8851 -5582
-7893 -8622 4210 -7213
9625 -446 -8443 -9850
-8938 -5388 -3843 320
1104 -5252 4319 9847
2861 -6366 7847 2754
-3371 -6987 1440 -3714
-8810 275 -1932 -5294
6323 4901 -9319 -6060
-9482 4308 -3820 2761
-7791 72 -7568 2794
-9896 1...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 1000 numbers

Test #23:

score: 0
Accepted
time: 435ms
memory: 18056kb

input:

814 7
-89 23 -61 5
39 94 -77 22
-46 97 72 -30
80 72 -31 -55
27 17 44 33
-22 79 -4 71
29 -32 24 1
-87 61 -46 -7
23 20 92 9
41 51 -70 -58
9 -40 65 87
-46 51 -72 44
-34 -49 100 27
-39 -61 7 22
-53 9 -5 87
10 -9 -82 -47
-6 59 -20 -1
-16 28 -81 32
87 68 -3 -5
-62 57 69 -67
76 16 51 62
42 38 97 98
-1 16 -...

output:

0.1350232140
0.0824155370
0.1453343332
0.0525219573
0.0824155370
0.0925943840
0.0420019573
0.0525219573
0.1530416001
0.0950081470
0.0645179775
0.0637437054
0.1597791374
0.0208763702
0.0183995146
0.0561944882
0.0045830710
0.2741576072
0.0420019573
0.1135031440
0.0627360715
0.0183995146
0.0925943840
0...

result:

ok 814 numbers

Test #24:

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

input:

470 6
-45 73 -59 -16
-76 3 47 81
-4 77 37 -49
18 50 -25 96
30 70 91 -66
-54 40 -13 50
66 59 -20 6
-75 -60 40 18
53 -18 -11 -93
1 66 31 -50
74 -47 -33 -30
-80 80 -62 -71
44 49 -21 -50
63 46 7 -24
50 21 -70 -43
-98 65 -26 -22
56 37 73 -77
-47 55 70 -46
49 27 78 -61
29 99 -70 61
-61 44 -75 10
-85 -61 -...

output:

0.3755186761
1.6683190319
0.5439754984
-1
2.2304230764
1.1530555754
1.1259959049
-1
1.5475600354
4.4069554660
-1
0.9666765818
-1
1.0774814125
0.9776803662
-1
-1
-1
0.4940316671
3.0154768339
2.6293825029
1.5907372637
-1
-1
0.6386590205
-1
0.0990639634
-1
-1
-1
1.8308600509
-1
-1
0.0739966176
-1
0.829...

result:

ok 470 numbers

Test #25:

score: 0
Accepted
time: 176ms
memory: 12888kb

input:

513 10
-21 18 -43 84
-74 -32 -68 -82
16 -98 -70 -10
98 -83 -38 -55
-85 -57 41 51
-41 -80 -50 -98
-92 -11 49 -64
16 91 53 -18
-50 86 14 -39
-76 42 -58 -26
37 -82 -20 -49
45 -81 -97 2
-22 -83 -32 84
98 -77 49 30
98 36 -45 92
-54 -90 18 -87
27 15 49 -63
-54 -67 -7 -59
-55 46 -36 91
-25 -63 31 90
7 9 -5...

output:

0.0366686664
0.0172286678
0.0186958309
0.0366686664
0.0363338409
0.0366686664
0.0000000000
0.0893839967
0.0042368327
0.0000000000
0.0000000000
0.0172286678
0.0186958309
0.0276413448
0.0288127413
0.0000000000
0.0366686664
0.0000000000
0.0172286678
0.0000000000
0.0276413448
0.0366686664
0.0363338409
0...

result:

ok 513 numbers

Test #26:

score: 0
Accepted
time: 183ms
memory: 12288kb

input:

532 6
-83 82 60 -25
86 28 4 42
17 27 13 -1
-90 -71 45 86
-49 79 -40 64
-1 -48 -97 -34
70 -33 57 20
100 -27 20 93
51 16 -13 -69
73 -43 28 -87
-10 48 38 89
95 13 -11 43
-82 -14 93 50
-78 100 96 -37
38 -55 89 -57
-65 41 77 23
91 30 66 -98
-30 89 24 42
43 75 38 91
87 51 -72 -56
69 -8 -1 -29
85 75 49 7
-...

output:

1.5172336224
1.1942063905
0.9516112444
0.6958175651
-1
-1
-1
-1
-1
1.0108431270
1.8880093688
0.7620942617
0.4746029822
-1
0.6434609350
-1
0.5598349757
4.8428588804
1.0661373076
2.2614397578
14.0077500610
0.6123377725
0.8682795994
2.7340660877
-1
0.8656817512
7.0049861881
6.5000000000
-1
0.7609504950...

result:

ok 532 numbers

Test #27:

score: 0
Accepted
time: 269ms
memory: 15516kb

input:

643 0
-1 34 -94 71
-66 69 18 -76
71 76 -3 20
-44 33 47 79
-83 -49 -33 -5
-9 -70 -95 -9
-26 70 -36 -49
66 96 -43 2
-36 -49 86 34
-11 27 -36 -64
-35 73 18 -93
45 -42 -56 47
77 -95 -77 7
1 6 -60 -30
-54 -50 -83 -76
97 68 -100 92
-33 -34 -25 71
-29 -55 -69 -26
23 -90 -20 -58
24 56 100 -88
-55 52 5 21
-6...

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 643 numbers

Test #28:

score: 0
Accepted
time: 273ms
memory: 15140kb

input:

649 4
-46 -57 -99 -52
31 38 10 70
43 -8 -41 -2
77 -59 39 8
-6 -35 26 -90
-3 54 -53 76
-81 92 -35 -3
-63 -29 27 46
-10 6 -25 53
95 -55 21 36
-43 31 -61 96
-44 41 14 -44
17 44 -70 47
-73 24 11 -4
61 -82 -58 -66
-78 -59 74 52
73 11 -71 -29
-63 95 31 -11
22 -39 -73 92
-32 -24 -99 74
-8 -38 -9 81
-45 83 ...

output:

-1
0.8225966476
3.6281719344
1.7512954496
-1
1.5375538616
0.1442504193
0.9853801471
2.3565044949
-1
0.6303594501
1.7557541922
1.1167504272
2.4824316148
0.1851867818
0.8616028350
1.2277612676
1.0929745488
-1
1.1008057175
3.5456580545
2.2680900670
1.4118146030
1.5976594150
-1
1.3667730454
0.7242105909...

result:

ok 649 numbers

Test #29:

score: 0
Accepted
time: 496ms
memory: 17844kb

input:

870 5
-74 75 99 -38
70 61 39 36
-34 55 -44 27
-54 -11 -41 48
-12 -77 -80 0
13 -100 -54 39
-100 51 -32 62
-79 37 54 44
-56 -65 79 63
-37 -22 -61 -18
-80 63 37 -78
70 15 1 66
45 -13 32 49
-89 40 -56 -74
90 42 -13 79
-89 -50 65 -54
-37 -61 -29 64
75 -71 -100 -18
-86 97 60 10
91 -49 -14 -89
-45 -31 56 6...

output:

3.1700062268
0.2544737770
0.7570098512
-1
1.4215415747
3.1923788910
0.3948239586
1.2396130782
3.8929906405
0.5174987966
2.0542532003
2.9687637429
2.8705387601
1.7612789665
-1
0.8513301677
4.0000000000
0.1411388552
-1
0.9659397310
1.4215415747
0.4772730213
4.4602451999
1.4365651949
1.2848172468
0.864...

result:

ok 870 numbers

Test #30:

score: 0
Accepted
time: 511ms
memory: 18400kb

input:

886 2
18 28 -29 23
-53 58 -66 82
-72 34 -75 -15
-18 45 3 33
89 79 -72 52
81 -7 -38 68
67 -88 17 -90
13 -79 -20 93
41 24 15 89
-85 -69 -27 -13
-48 -22 95 91
-90 -16 -95 43
1 52 62 -70
-27 33 5 63
-30 -52 -67 -60
34 -80 -29 -42
-71 26 23 9
99 -9 -38 99
16 -50 25 66
94 -11 -24 18
43 56 -11 -14
-90 -20 ...

output:

-1
-1
1.9377863274
6.7297035785
-1
-1
1.0123723119
7.6617693983
-1
0.5533869713
-1
0.2471403276
4.0000000000
-1
-1
2.3868455595
-1
0.7652216500
3.6231899942
0.7683228054
-1
1.4746117983
0.6368142977
-1
0.8096163282
-1
-1
-1
5.3187572848
0.3723003844
-1
2.3051418068
-1
-1
-1
-1
0.5080878883
-1
-1
-1
...

result:

ok 886 numbers

Test #31:

score: 0
Accepted
time: 65ms
memory: 8548kb

input:

314 0
-46 2 53 -80
49 62 32 86
-85 19 -55 -75
41 85 12 78
66 -41 -34 -78
26 -67 -50 93
-32 76 -98 53
55 63 75 60
100 51 -92 57
34 -52 -59 27
90 -38 37 -43
66 -33 -5 -70
57 22 50 92
-5 68 -77 16
23 -31 44 -35
-67 65 -21 -8
98 59 -22 -97
-42 68 35 44
30 69 56 -77
67 -81 -76 82
-42 -56 43 72
85 0 18 98...

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 314 numbers

Test #32:

score: 0
Accepted
time: 437ms
memory: 18724kb

input:

821 3
10 63 -66 4
24 -76 -46 -4
-59 -28 -15 62
-95 94 22 -20
-2 -77 25 42
-56 47 -28 -45
-77 4 -79 -61
76 10 -25 -69
29 -74 24 50
72 -32 -38 50
-89 -34 -27 12
46 81 -25 6
-99 9 -31 -57
16 -84 79 10
-95 -31 -41 -6
-60 28 19 98
-63 68 -55 -78
62 40 -64 39
19 -91 83 -69
97 99 3 -18
-98 0 -48 100
-100 -...

output:

1.7962088323
10.8340984555
1.1786287396
1.2095687597
1.7509492949
-1
-1
1.2532855059
1.0054952700
1.8509232569
0.6538674269
3.4969474274
-1
23.2899426536
1.3287879308
-1
0.4702788970
-1
1.3444249018
-1
-1
1.6242524820
4.5122503355
1.6377358491
-1
1.4759929837
0.4775670140
-1
5.0142737299
7.113255824...

result:

ok 821 numbers

Test #33:

score: 0
Accepted
time: 429ms
memory: 17548kb

input:

808 8
-80 3 -66 -24
-53 -29 42 -58
93 -74 50 -63
34 -59 49 81
47 -33 -25 2
-48 -29 18 -94
-67 -71 -43 -39
69 20 -32 -85
3 12 -80 -93
-78 8 67 -84
-49 -10 37 -42
-56 -46 37 55
-61 94 40 -14
88 -6 32 75
59 49 -20 -64
-53 70 92 -68
44 46 35 62
-18 -83 26 57
65 1 -70 6
-35 -73 -59 98
-51 18 -74 37
4 49 ...

output:

0.0013040124
0.1187803576
0.0480814123
0.0480814123
0.0013040124
0.0000000000
0.0464113697
0.0321167685
0.0000000000
0.0000000000
0.0000000000
0.0075394534
0.0464113697
0.0566271236
0.0075394534
0.0566271236
0.0000000000
0.0464113697
0.0000000000
0.0000000000
0.0249900884
0.0000000000
0.0631030829
0...

result:

ok 808 numbers

Test #34:

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

input:

413 4
91 0 -98 -23
-48 -54 -45 56
-35 -68 -35 -42
-10 23 58 19
-61 48 88 10
36 84 65 -68
-59 -72 3 9
-79 2 93 76
17 -92 -14 -35
-43 -4 20 27
-92 25 -87 -95
-14 -22 -44 45
33 -62 11 4
25 -51 98 60
-84 95 41 -29
25 4 -94 -31
44 -42 54 -11
-31 -22 -45 -80
-14 85 18 38
28 14 -75 -86
73 -75 15 -5
-26 -16...

output:

-1
-1
0.8501750517
1.0811004144
1.0290454260
-1
1.5915161007
2.2241057891
1.3003616630
-1
2.5416666667
1.3169147944
0.4371815924
1.6612907605
-1
-1
-1
-1
-1
1.8488042182
-1
2.5069981239
1.1034965631
-1
-1
2.9177764599
0.3691875448
-1
3.6496948543
1.5357450855
-1
3.4597315436
-1
0.3307502568
-1
0.761...

result:

ok 413 numbers

Test #35:

score: 0
Accepted
time: 215ms
memory: 14752kb

input:

578 3
-18 38 16 -85
92 -92 -60 -13
80 0 -57 35
-66 -36 36 -56
-28 100 8 -32
48 86 -10 -31
73 51 28 -40
-21 -14 18 23
-36 62 -5 -84
13 -87 7 -14
72 5 33 65
-4 -99 20 31
15 27 85 -29
-11 -75 -39 34
95 83 3 -3
25 77 40 94
13 0 58 52
79 41 -18 -31
29 -21 65 -21
-53 -41 14 -36
15 99 -15 9
-68 10 -42 -67
...

output:

-1
0.7638175741
2.4556619665
1.1208796886
1.1255824545
-1
0.4614387415
0.2097659611
1.8059366635
1.8719841560
1.5973396251
-1
1.4245269886
3.3084137280
-1
1.8698706242
1.0194919598
2.6523006354
1.7533738256
0.7745698551
-1
-1
-1
0.7193104248
5.8888888889
0.6917056114
0.1838881298
2.2572038208
0.9674...

result:

ok 578 numbers

Test #36:

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

input:

208 2
88 -93 -47 42
-25 -53 70 -5
-94 65 69 27
-73 -16 42 66
50 87 -11 78
-68 -93 89 -68
83 73 85 -27
-57 25 83 -40
0 28 -97 -56
69 25 -99 -13
18 -58 17 -72
-24 60 -93 83
-98 -38 81 -71
34 78 2 -80
85 47 56 58
-55 51 -68 85
-6 -31 -3 -5
-47 54 72 72
4 29 40 60
73 -18 -93 -67
-81 20 52 -10
-2 42 -83 ...

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 208 numbers

Test #37:

score: 0
Accepted
time: 501ms
memory: 17608kb

input:

874 4
18 -85 -98 63
35 86 12 -27
-25 -71 68 56
100 41 11 47
-71 -13 -65 84
-24 18 -3 28
92 67 -27 86
-100 -55 -36 37
-29 -80 89 -45
-16 -56 36 14
-76 54 46 -45
-4 28 22 72
-54 -2 -68 -74
-48 -82 23 -69
57 16 -32 -64
41 -2 -94 -5
28 -78 -99 -82
-88 -23 -24 70
20 -81 -86 52
-82 -100 -68 13
96 -88 -53 ...

output:

-1
0.5368103800
-1
-1
-1
-1
3.6226650884
0.2685809425
0.3983479821
1.1820918758
-1
-1
1.6374190406
0.8517360731
1.4331308798
0.1728749228
-1
0.2373868683
-1
1.2294472861
1.4399661802
4.8572627464
-1
1.0000000000
1.2997870655
-1
0.5628162552
6.7042147785
1.7334135213
-1
2.0712896964
-1
-1
0.623674017...

result:

ok 874 numbers

Test #38:

score: 0
Accepted
time: 437ms
memory: 17328kb

input:

809 10
-58 -92 67 71
-16 69 -91 97
56 94 -80 -41
-33 100 -18 71
76 85 88 -100
-44 79 13 -5
100 -47 -90 31
-46 19 27 -3
-50 -6 29 69
37 -67 -57 -97
-34 66 -7 -100
59 58 -74 78
-31 -13 -84 -46
-11 96 -30 56
-38 46 93 29
44 -73 97 -37
40 -40 94 72
71 38 -23 -24
-5 60 53 36
42 18 -62 -64
20 66 -21 -29
2...

output:

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0...

result:

ok 809 numbers

Test #39:

score: 0
Accepted
time: 390ms
memory: 16700kb

input:

776 0
-51 73 79 35
83 -98 80 -32
-53 -99 36 -35
-74 -5 -49 -32
-69 -27 17 -30
29 -15 28 2
-23 65 -45 -56
-45 -33 68 -36
-33 87 14 -65
-80 -54 20 -83
14 58 -100 -4
7 87 -88 -71
11 87 84 -84
-6 -78 61 -83
36 -54 -28 21
-100 73 -50 97
-96 28 61 -27
-67 26 88 -94
32 61 -64 69
-10 48 -38 -38
-77 -38 94 9...

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 776 numbers

Test #40:

score: 0
Accepted
time: 399ms
memory: 16884kb

input:

778 5
-3 -7 89 -79
-7 48 -77 66
71 -3 -64 -45
43 -88 55 -63
73 48 -48 54
-16 55 4 5
63 21 68 63
-58 80 -45 -7
-79 83 57 -35
-61 51 -24 84
-29 -16 89 5
-55 -33 55 21
-33 100 -43 11
-11 -30 2 -91
80 27 -71 75
99 -70 2 -23
-93 8 -21 76
-10 -95 88 11
-34 15 6 -10
93 71 51 -41
9 32 -71 -81
56 -83 -10 -77...

output:

6.2372554488
0.3994549302
6.8550781096
-1
0.9000000000
-1
1.6496344978
0.7794255141
6.4000000000
0.1578440544
0.3149840188
1.7022262487
0.4244458696
1.9769945249
1.1152838304
1.5121880486
1.1285892672
0.5359856138
1.9749752885
0.2669853351
-1
0.3258193565
-1
0.1688243525
1.3054896939
0.9059699175
-1...

result:

ok 778 numbers

Test #41:

score: 0
Accepted
time: 24ms
memory: 6540kb

input:

187 3
-72 65 90 85
-17 38 23 -53
-4 -33 -18 -24
-13 -61 34 37
64 75 21 -20
0 -90 -51 -9
-21 64 2 82
100 82 40 46
95 62 33 -41
21 -73 -90 -23
-5 26 -58 -13
87 -72 -18 -66
96 97 3 -9
74 39 -25 28
17 -52 -3 -29
90 76 -36 68
70 -96 -16 21
-94 -42 -70 24
69 68 -64 2
-19 -91 45 4
28 -64 -90 -48
44 -4 48 -...

output:

-1
-1
-1
-1
-1
0.5645365605
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4.6108554958
-1
-1
0.1818490256
-1
-1
-1
-1
-1
0.7695593624
-1
1.1266063671
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0.2450746406
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0.2809568615
-1
-1
-1
-1
-1
0.174026...

result:

ok 187 numbers

Test #42:

score: 0
Accepted
time: 21ms
memory: 6620kb

input:

176 1
-75 -91 30 -70
-94 -85 -63 -8
-62 -88 96 37
8 7 -15 -12
-21 82 -2 -95
-75 27 -18 -85
89 -100 93 65
-36 63 3 -74
-29 -42 9 77
-34 41 10 -49
0 -14 20 39
-41 -11 -51 66
-31 -17 9 -86
-4 70 77 -12
-30 82 -100 -63
-60 -23 43 94
90 -45 81 90
-81 87 -36 90
21 -76 29 89
80 -57 -53 30
-45 -58 27 76
-37...

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 176 numbers

Test #43:

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

input:

1 10000
0 0 10000 1
10000 1 -10000 -1

output:

0.0000000025

result:

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

Test #44:

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

input:

1 1
-10000 10000 10000 0
-10000 -10000 10000 1

output:

19999.0000000000

result:

ok found '19999.0000000', expected '19999.0000000', error '0.0000000'

Test #45:

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

input:

2 5
-6 -8 27 36
0 1 0 -9
-6 8 27 -36

output:

0.1111111111
0.1111111111

result:

ok 2 numbers