QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594341#6599. The Grand TournamentRillloAC ✓239ms4072kbC++237.2kb2024-09-27 21:46:002024-09-27 21:46:01

Judging History

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

  • [2024-09-27 21:46:01]
  • 评测
  • 测评结果:AC
  • 用时:239ms
  • 内存:4072kb
  • [2024-09-27 21:46:00]
  • 提交

answer

// HNOI2007, 最小矩形覆盖
// http://oj.daimayuan.top/course/30/problem/1208
#include<bits/stdc++.h>
#define rep(i,s,t) for (int i = s; i < t; i++)
using i64 = long long;
using db = double;
const db EPS = 1e-12;
  
inline int sign(db a) { return a < -EPS ? -1 : a > EPS; }
  
inline int cmp(db a, db b) { return sign(a - b); }
  
struct P {
	db x, y;
	P() {}
	P(db _x, db _y) : x(_x), y(_y) {}
	P operator+(P p) { return {x + p.x, y + p.y}; }
	P operator-(P p) { return {x - p.x, y - p.y}; }
	P operator*(db d) { return {x * d, y * d}; }
	P operator/(db d) { return {x / d, y / d}; }

    // 按 x 然后 y 进行比较
	bool operator<(P p) const { 
		int c = cmp(x, p.x);
		if (c) return c == -1;
		return cmp(y, p.y) == -1;
	}

	bool operator==(P o) const{
		return cmp(x,o.x) == 0 && cmp(y,o.y) == 0;
	}

	db dot(P p) { return x * p.x + y * p.y; }
	db det(P p) { return x * p.y - y * p.x; }
	 
	db distTo(P p) { return (*this - p).abs(); }
	db alpha() { return std::atan2(y, x); }
	void read() { std::cin >> x >> y; }
	void write() {std::cout << "(" << x << ", " << y << ")" << "\n";}
	db abs() { return std::sqrt(abs2()); }
	db abs2() { return x * x + y * y; }
	P rot90() { return P(-y,x);}
	P unit() { return *this / abs(); }
	int quad() const { return sign(y) == 1 || (sign(y) == 0 && sign(x) >= 0); }
	P rot(db an){ return { x * std::cos(an) - y * std::sin(an), x * std::sin(an) + y * std::cos(an)}; }
};

// p1p2 和 p1p3 的叉积
#define cross(p1, p2, p3) ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y))
// 顺时针还是逆时针还是共线
#define crossOp(p1, p2, p3) sign(cross(p1, p2, p3))
 
// 直线 p1p2, q1q2 是否恰有一个交点
bool chkLL(P p1, P p2, P q1, P q2) {
	db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return sign(a1 + a2) != 0;
}

// 求直线 p1p2, q1q2 的交点
P isLL(P p1, P p2, P q1, P q2) {
	db a1 = cross(q1, q2, p1), a2 = -cross(q1, q2, p2);
	return (p1 * a2 + p2 * a1) / (a1 + a2);
}

// 判断区间 [l1, r1], [l2, r2] 是否相交
bool intersect(db l1,db r1,db l2,db r2){
	if (l1>r1) std::swap(l1,r1); if (l2>r2) std::swap(l2,r2); 
	return !( cmp(r1,l2) == -1 || cmp(r2,l1) == -1 );
}

// 线段 p1p2, q1q2 相交
bool isSS(P p1, P p2, P q1, P q2){
	return intersect(p1.x,p2.x,q1.x,q2.x) && intersect(p1.y,p2.y,q1.y,q2.y) && 
	crossOp(p1,p2,q1) * crossOp(p1,p2,q2) <= 0 && crossOp(q1,q2,p1)
			* crossOp(q1,q2,p2) <= 0;
}

// 线段 p1p2, q1q2 严格相交  
bool isSS_strict(P p1, P p2, P q1, P q2){
	return crossOp(p1,p2,q1) * crossOp(p1,p2,q2) < 0 && crossOp(q1,q2,p1)
			* crossOp(q1,q2,p2) < 0;
}

// m 在 a 和 b 之间
bool isMiddle(db a, db m, db b) {
	/*if (a > b) std::std::swap(a, b);
	return cmp(a, m) <= 0 && cmp(m, b) <= 0;*/
	return sign(a - m) == 0 || sign(b - m) == 0 || (a < m != b < m);
}

bool isMiddle(P a, P m, P b) {
	return isMiddle(a.x, m.x, b.x) && isMiddle(a.y, m.y, b.y);
}

// 点 p 在线段 p1p2 上
bool onSeg(P p1, P p2, P q){
	return crossOp(p1,p2,q) == 0 && isMiddle(p1, q, p2);
}
// q1q2 和 p1p2 的交点 在 p1p2 上?

// 点 p 严格在 p1p2 上
bool onSeg_strict(P p1, P p2, P q){
	return crossOp(p1,p2,q) == 0 && sign((q-p1).dot(p1-p2)) * sign((q-p2).dot(p1-p2)) < 0;
}

// 求 q 到 直线p1p2 的投影(垂足) ⚠️ : p1 != p2
P proj(P p1, P p2, P q) {
	P dir = p2 - p1;
	return p1 + dir * (dir.dot(q - p1) / dir.abs2());
}
// 求 q 以 直线p1p2 为轴的反射
P reflect(P p1, P p2, P q){
	return proj(p1,p2,q) * 2 - q;
}

// 求 q 到 线段p1p2 的最小距离
db nearest(P p1, P p2, P q){
	if (p1 == p2) return p1.distTo(q);
	P h = proj(p1,p2,q);
	if(isMiddle(p1,h,p2))
		return q.distTo(h);
	return std::min(p1.distTo(q),p2.distTo(q));
}

// 求 线段p1p2 与 线段q1q2 的距离
db disSS(P p1, P p2, P q1, P q2){
	if(isSS(p1,p2,q1,q2)) return 0;
	return std::min(std::min(nearest(p1,p2,q1),nearest(p1,p2,q2)), std::min(nearest(q1,q2,p1),nearest(q1,q2,p2)));
}
db area(std::vector<P> ps){
	db ret = 0; rep(i,0,ps.size()) ret += ps[i].det(ps[(i+1)%ps.size()]); 
	return ret/2;
}
  
int contain(std::vector<P> ps, P p){ //2:inside,1:on_seg,0:outside
	int n = ps.size(), ret = 0; 
	rep(i,0,n){
		P u=ps[i],v=ps[(i+1)%n];
		if(onSeg(u,v,p)) return 1;
		if(cmp(u.y,v.y)<=0) std::swap(u,v);
		if(cmp(p.y,u.y) > 0 || cmp(p.y,v.y) <= 0) continue;
		ret ^= crossOp(p,u,v) > 0;
	}
	return ret*2;
}
  
std::vector<P> convexHull(std::vector<P> ps) {
	int n = ps.size(); if(n <= 1) return ps;
	std::sort(ps.begin(), ps.end());
	std::vector<P> qs(n * 2); int k = 0;
	for (int i = 0; i < n; qs[k++] = ps[i++]) 
		while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
		while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) <= 0) --k;
	qs.resize(k - 1);
	return qs;
}
  
std::vector<P> convexHullNonStrict(std::vector<P> ps) {
	//caution: need to unique the Ps first
	int n = ps.size(); if(n <= 1) return ps;
	std::sort(ps.begin(), ps.end());
	std::vector<P> qs(n * 2); int k = 0;
	for (int i = 0; i < n; qs[k++] = ps[i++]) 
		while (k > 1 && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
	for (int i = n - 2, t = k; i >= 0; qs[k++] = ps[i--])
		while (k > t && crossOp(qs[k - 2], qs[k - 1], ps[i]) < 0) --k;
	qs.resize(k - 1);
	return qs;
}
  
db convexDiameter(std::vector<P> ps){
	int n = ps.size(); if(n <= 1) return 0;
	int is = 0, js = 0; rep(k,1,n) is = ps[k]<ps[is]?k:is, js = ps[js] < ps[k]?k:js;
	int i = is, j = js;
	db ret = ps[i].distTo(ps[j]);
	do { 
		if ((ps[(i+1)%n]-ps[i]).det(ps[(j+1)%n]-ps[j]) >= 0)
			(++j)%=n;
		else
			(++i)%=n;
		ret = std::max(ret,ps[i].distTo(ps[j]));
	} while(i!=is || j!=js);
	return ret;
}
  
std::vector<P> convexCut(const std::vector<P> &ps, P q1, P q2) {
	std::vector<P> qs;
	int n = ps.size();
	rep (i, 0, n) {
		P p1 = ps[i], p2 = ps[(i+1)%n];
		int d1 = crossOp(q1,q2,p1), d2 = crossOp(q1,q2,p2);
		if(d1 >= 0) qs.push_back(p1);
		if(d1 * d2 < 0) qs.push_back(isLL(p1,p2,q1,q2));
	}
	return qs;
}

void solve() {
    P ld, ru;
    ld.read(), ru.read();
    P lu = {ld.x, ru.y};
    P rd = {ru.x, ld.y};
    
    P q[2], p[2];
    p[0].read(), p[1].read();
    q[0].read(), q[1].read();

    std::vector<P> reac{ld, rd, ru, lu};
    db ans = 0;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            if (!(p[i] == q[j])) continue;
            auto r = convexCut(reac, p[i], p[i] + (p[i ^ 1] - p[i]).rot90());
            r = convexCut(r, q[j], q[j] + (q[j ^ 1] - q[j]).rot90());
            ans += area(r);   
        }
    }

    // std::cout << ans << "\n";
    if (crossOp(p[0], p[1], q[0]) == 0 && crossOp(p[0], p[1], q[1]) == 0) {
        reac = convexCut(reac, p[1], p[1] + (p[1] - p[0]).rot90());
        reac = convexCut(reac, p[0], p[0] + (p[0] - p[1]).rot90());
        reac = convexCut(reac, q[1], q[1] + (q[1] - q[0]).rot90());
        reac = convexCut(reac, q[0], q[0] + (q[0] - q[1]).rot90());
        ans += area(reac);
    }
    std::cout << ans << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::fixed << std::setprecision(10);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    } 
    return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
0 0 3 3
1 1 1 2
2 1 2 2
0 0 3 3
1 1 1 2
1 2 2 2

output:

0.0000000000
1.0000000000

result:

ok 2 numbers

Test #2:

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

input:

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

output:

0.0000000000
3.7500000000
0.0000000000
6.0000000000
0.0000000000
0.0000000000
0.0000000000
6.0000000000
2.0000000000
4.0000000000

result:

ok 10 numbers

Test #3:

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

input:

100000
350 720 355 732
353 725 352 729
354 721 353 725
-807 606 -801 621
-803 608 -803 616
-803 616 -803 614
-389 463 -373 466
-382 464 -387 464
-387 464 -385 464
-664 801 -655 806
-656 803 -659 803
-659 803 -657 802
896 -767 901 -762
900 -763 897 -763
900 -763 897 -763
403 645 407 652
406 647 405 6...

output:

0.0000000000
42.0000000000
12.0000000000
24.0000000000
25.0000000000
28.0000000000
99.0000000000
0.0000000000
135.0000000000
6.0000000000
42.0000000000
45.0000000000
120.0000000000
8.0000000000
84.0000000000
15.0000000000
16.0000000000
0.0000000000
36.0000000000
4.0000000000
0.5000000000
20.00000000...

result:

ok 100000 numbers

Test #4:

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

input:

100000
-653 -979 -650 -961
-652 -973 -651 -973
-652 -973 -651 -973
-311 -975 -297 -966
-301 -967 -309 -973
-309 -973 -301 -967
734 -459 746 -420
736 -451 743 -440
736 -451 743 -440
127 431 139 456
131 436 138 447
138 447 131 436
-535 293 -505 299
-510 296 -531 297
-510 296 -533 295
571 -397 584 -371...

output:

54.0000000000
126.0000000000
468.0000000000
300.0000000000
29.5900621118
190.6666666667
75.0000000000
0.0000000000
323.0000000000
0.0000000000
0.0000000000
18.0000000000
0.0000000000
141.2894736842
29.3076923077
21.0000000000
7.7500000000
20.0000000000
3.1000000000
144.0000000000
1.5833333333
0.0000...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 222ms
memory: 3824kb

input:

100000
-553 286 -544 299
-551 297 -552 288
-551 297 -548 293
-535 81 -526 122
-534 86 -532 117
-532 117 -534 86
42 -110 54 -94
43 -95 47 -109
47 -109 45 -102
392 33 397 38
395 36 394 37
394 37 395 36
-934 910 -916 933
-924 915 -933 916
-917 921 -933 916
-119 -981 -87 -975
-90 -980 -114 -980
-103 -97...

output:

6.4444444444
369.0000000000
106.2857142857
25.0000000000
5.6000000000
0.0000000000
32.0000000000
216.0000000000
0.0000000000
99.9000000000
0.0000000000
6.0000000000
276.6500000000
0.0000000000
462.0000000000
42.0000000000
0.0000000000
0.0000000000
1710.0000000000
0.0000000000
50.0000000000
245.00000...

result:

ok 100000 numbers

Test #6:

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

input:

100000
587 345 644 380
643 368 595 358
643 368 595 358
361 362 367 379
362 373 364 368
364 368 366 363
-418 766 -374 819
-410 796 -403 813
-417 779 -403 813
-536 183 -488 322
-510 238 -521 222
-521 222 -532 304
719 393 812 421
728 417 808 420
728 417 808 420
209 -634 242 -618
231 -623 238 -626
238 -...

output:

1995.0000000000
0.0000000000
1265.6470588235
1482.5647865854
2604.0000000000
528.0000000000
384.0000000000
481.6307692308
0.0000000000
490.0000000000
70.0000000000
0.0000000000
16.0000000000
270.0000000000
597.4545454545
288.0000000000
0.0000000000
1206.6250000000
512.0000000000
1.0763888889
1458.00...

result:

ok 100000 numbers

Test #7:

score: 0
Accepted
time: 231ms
memory: 3816kb

input:

100000
-77 35 -66 122
-69 98 -72 81
-72 81 -69 70
-804 257 -551 278
-656 269 -794 277
-656 269 -587 265
-311 610 -280 731
-306 638 -288 700
-306 638 -288 700
-438 472 -433 615
-437 536 -437 499
-437 499 -437 536
-295 -71 -213 39
-275 -29 -238 34
-275 -29 -238 34
589 387 728 432
646 394 631 407
616 4...

output:

5.6149732620
0.0000000000
3751.0000000000
715.0000000000
9020.0000000000
0.0000000000
14300.0000000000
16364.2741935484
50801.4838709677
16.0000000000
0.0000000000
2493.6363636364
280.6607142857
44.0000000000
185.0000000000
935.0000000000
9.4659090909
56.0000000000
4726.0000000000
437.1000000000
466...

result:

ok 100000 numbers

Test #8:

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

input:

100000
-475 589 -253 919
-408 663 -351 817
-408 663 -351 817
524 632 561 857
553 829 556 729
541 765 559 807
-253 -540 -98 -505
-239 -506 -232 -510
-239 -506 -232 -510
-149 639 -51 649
-130 647 -87 644
-130 647 -87 644
719 -478 924 92
916 -66 920 74
910 -276 912 -206
-75 -924 -47 -677
-66 -844 -48 -...

output:

73260.0000000000
0.0000000000
5425.0000000000
980.0000000000
0.0000000000
4692.4705882353
651.0000000000
560.0000000000
21645.0000000000
1013.2467850582
32053.0000000000
96819.0000000000
31937.1755890762
168.0000000000
260.0000000000
2398.3780487805
8256.0000000000
0.0000000000
0.0000000000
14500.30...

result:

ok 100000 numbers

Test #9:

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

input:

100000
-302 -975 987 976
-25 289 396 -1
21 -703 930 -131
-993 -999 968 963
-381 -323 929 583
487 -43 -303 -356
-700 -827 301 846
-366 742 -570 319
-570 319 -638 178
401 -174 675 180
463 -149 455 -131
463 -149 459 -140
-133 -812 454 808
221 176 145 537
121 651 145 537
-334 -930 781 -18
638 -504 279 -...

output:

0.0000000000
0.0000000000
0.0000000000
18936.4444444444
0.0000000000
1016880.0000000000
602.1705458741
509410.0000000000
0.0000000000
177747.8083832335
240642.3387096774
369120.7786144578
0.0000000000
538241.0000000000
0.0000000000
0.0000000000
0.0000000000
257258.7829787234
339529.6515789474
477372...

result:

ok 100000 numbers

Test #10:

score: 0
Accepted
time: 237ms
memory: 3824kb

input:

100000
-979 -985 824 957
559 390 -209 191
313 140 -209 191
-803 -976 928 979
686 -661 -676 876
686 -661 -676 876
-930 -993 896 995
519 318 -16 230
-16 230 519 318
-625 -850 969 915
540 -88 575 572
526 -352 561 308
-840 -977 839 946
122 -658 -670 403
-670 403 122 -658
-994 -1000 951 1000
383 -468 211...

output:

1351762.3093570403
3384105.0000000000
3630088.0000000000
632999.1363636362
3228717.0000000000
867642.8888888888
0.0000000001
3506074.0000000005
3256160.0000000000
3230766.0000000000
3144390.0000000000
3487423.9999999995
0.0000000000
0.0000000000
2231056.0000000000
3827620.0000000000
2734851.41414444...

result:

ok 100000 numbers

Test #11:

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

input:

100000
-998 -998 997 994
-271 -892 885 154
501 -277 -539 313
-992 -993 977 998
-240 190 -155 863
107 43 -449 362
-992 -1000 996 1000
-498 586 530 -270
-813 478 787 -484
-999 -990 994 999
328 -701 -484 -425
328 -701 -484 -425
-998 -999 997 994
-559 439 929 299
185 369 929 299
-1000 -999 994 999
766 -...

output:

0.0000000000
0.0000000000
0.0000000000
3964077.0000000000
1687977.2432795698
3984012.0000000005
1186.8072701491
3769116.0000000000
3972033.0000000000
2145411.9341637008
0.0000000000
2031273.5632183906
769194.2585470084
1829984.5090909090
2233806.7532097003
3958054.0000000000
164249.7130102041
205535...

result:

ok 100000 numbers

Test #12:

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

input:

100000
329 -90 334 -72
332 -89 332 -88
332 -89 332 -88
-211 427 -208 432
-209 428 -210 430
-209 428 -210 430
277 218 283 223
281 222 280 220
281 222 280 220
117 -745 128 -740
118 -744 127 -743
127 -743 118 -744
-438 172 -429 184
-437 177 -431 177
-431 176 -436 177
-406 529 -403 535
-405 530 -405 531...

output:

90.0000000000
15.0000000000
30.0000000000
55.0000000000
0.0000000000
18.0000000000
0.6666666667
9.0000000000
0.0000000000
11.3750000000
1.2500000000
15.0000000000
352.0000000000
0.0000000000
0.0000000000
80.0000000000
0.0000000000
12.0000000000
56.0000000000
0.0000000000
2.5000000000
0.0000000000
4....

result:

ok 100000 numbers

Test #13:

score: 0
Accepted
time: 225ms
memory: 3860kb

input:

100000
864 -604 868 -586
867 -598 866 -587
867 -601 866 -587
-973 -363 -967 -352
-971 -354 -969 -358
-968 -360 -968 -361
731 -847 734 -835
732 -845 733 -845
733 -845 732 -845
322 -154 356 -147
352 -148 342 -148
345 -148 355 -148
12 -593 16 -571
13 -580 14 -586
15 -592 13 -580
-665 293 -660 296
-663 ...

output:

3.9610389611
0.0000000000
36.0000000000
49.0000000000
60.0000000000
15.0000000000
71.5000000000
0.0000000000
40.0000000000
36.0000000000
104.0000000000
24.0000000000
12.0000000000
48.0000000000
0.0000000000
6.0000000000
12.0000000000
130.0000000000
112.0000000000
0.6000000000
88.0000000000
88.000000...

result:

ok 100000 numbers

Test #14:

score: 0
Accepted
time: 223ms
memory: 3872kb

input:

100000
11 -579 21 -575
14 -578 15 -576
14 -578 15 -576
638 916 653 935
650 925 650 929
650 918 650 927
207 -519 210 -495
209 -504 209 -499
209 -517 209 -503
-892 533 -879 547
-886 535 -891 545
-886 535 -891 545
24 -431 48 -381
25 -385 45 -415
45 -415 41 -397
-260 675 -253 742
-254 711 -257 731
-257 ...

output:

40.0000000000
30.0000000000
3.0000000000
182.0000000000
238.0000000000
469.0000000000
3.0210526315
85.0000000000
0.0000000000
2304.0000000000
5.0000000000
48.0000000000
732.0000000001
272.0000000000
0.0000000000
0.0000000000
0.0000000000
378.0000000000
387.0000000000
12.8333333333
357.9545454545
0.0...

result:

ok 100000 numbers

Test #15:

score: 0
Accepted
time: 225ms
memory: 3896kb

input:

100000
233 -984 278 -977
237 -981 238 -979
236 -983 238 -979
612 814 628 829
622 824 627 818
622 824 627 818
948 403 965 406
953 404 951 405
951 405 953 404
-709 840 -551 862
-701 861 -630 847
-630 847 -701 861
536 523 543 534
537 524 541 525
541 525 537 524
-63 -483 -49 -466
-50 -477 -52 -480
-52 -...

output:

290.0000000000
240.0000000000
51.0000000000
3475.9999999999
77.0000000000
8.5714285714
0.0000000000
1092.0000000000
2662.0000000000
187.8500000000
836.0000000000
960.0000000000
0.0000000000
0.0000000000
861.8000000000
2171.7142857143
12463.0000000000
0.0000000000
159.2500000000
320.0000000000
198.00...

result:

ok 100000 numbers

Test #16:

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

input:

100000
725 209 729 214
727 210 726 211
726 211 727 210
660 -376 740 -226
738 -238 709 -291
738 -238 709 -291
149 -399 200 -264
196 -298 186 -384
196 -298 186 -384
312 -847 455 -765
390 -772 426 -813
426 -813 390 -772
947 -739 957 -632
956 -685 955 -693
955 -693 950 -733
-30 -883 -23 -878
-29 -882 -2...

output:

20.0000000000
12000.0000000000
6885.0000000000
11726.0000000000
0.0000000000
8.0000000000
612.0000000000
0.0000000000
1180.0000000000
19234.0000000000
0.0000000000
0.0000000000
0.0000000000
5896.0000000000
0.0000000000
3213.0000000000
492.0000000000
0.0000000000
0.0000000000
1838.2000000000
0.000000...

result:

ok 100000 numbers

Test #17:

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

input:

100000
-382 62 -103 103
-249 90 -246 99
-155 84 -246 99
-216 2 -111 48
-209 5 -153 3
-140 32 -166 39
-266 326 -109 379
-183 354 -208 346
-208 346 -183 354
-398 -169 327 192
-305 69 190 -164
-305 69 190 -164
-611 -877 -385 -717
-529 -784 -413 -775
-529 -784 -413 -775
-356 -68 -258 -48
-279 -49 -336 -...

output:

25.3186813187
0.0000000000
8321.0000000000
261725.0000000000
36160.0000000000
0.0000000000
148708.0000000000
1048.6842105263
33420.5581395349
23546.0000000000
6453.8478070175
1156.0000000000
17.9649122807
629.7870370370
24010.8363636364
2430.0000000000
0.0000000000
3251.3062500000
1090.4000000000
55...

result:

ok 100000 numbers

Test #18:

score: 0
Accepted
time: 238ms
memory: 3820kb

input:

100000
-670 -906 906 875
76 659 787 -116
787 -116 76 659
-512 346 718 508
87 409 344 492
657 449 344 492
-129 -479 474 487
234 -281 374 -23
29 357 164 -410
-370 -981 -168 987
-310 377 -198 -801
-310 377 -224 985
-919 -182 943 834
-465 389 -403 402
-403 402 -217 441
-550 -982 -534 418
-542 -847 -542 ...

output:

2806856.0000000000
58.9231859375
0.0000000000
425.7427843803
0.0000000000
22400.0000000000
415800.0000000001
0.0000000000
813732.0000000001
1094143.9407744873
442188.0000000000
0.0000000000
0.0000000000
0.0000000000
62167.3398058253
1417705.4045385781
0.0000000000
495772.6810176126
0.0000000000
1947...

result:

ok 100000 numbers

Test #19:

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

input:

100000
-1000 -857 805 872
303 182 -659 649
-659 649 303 182
-983 -960 901 944
-346 -598 -518 380
-432 -109 -604 869
-997 -952 965 920
733 -238 -389 -846
733 -238 -389 -846
-956 -970 980 994
-247 824 -479 664
-566 604 -305 784
-975 -746 883 894
-338 217 -827 497
-827 497 151 -63
-791 -588 946 900
202...

output:

3120845.0000000000
949771.0184049079
3672864.0000000000
504273.9310344826
910394.5194274028
2584656.0000000000
0.0000000000
3346200.0000000000
3722814.0000000005
0.0000000000
3455808.0000000000
3381192.0000000000
3000370.0000000000
0.0000000000
0.0000000000
453073.4246686304
1196461.7462932456
44668...

result:

ok 100000 numbers

Test #20:

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

input:

100000
-1000 -999 1000 998
339 -905 140 -133
140 -133 657 231
-992 -982 991 998
-250 -429 -135 -67
-365 -791 -250 -429
-966 -976 980 981
303 -92 106 -551
303 -92 106 -551
-997 -992 996 997
793 744 -740 -330
282 386 -229 28
-1000 -999 999 993
333 573 -767 222
333 573 -767 222
-981 -985 999 993
-273 -...

output:

1006535.9998797366
0.0000000000
3808322.0000000000
1470130.7832161717
3982007.9999999995
298549.5652173914
3548251.8828539290
1288381.2660803781
3876561.0000000000
0.0000000000
253344.0000000000
0.0000000000
0.0000000000
49050.5323689699
464519.0254521787
3924279.9999999995
3172778.5083701462
0.0000...

result:

ok 100000 numbers

Test #21:

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

input:

100000
52 -610 56 -606
54 -608 55 -607
55 -608 53 -607
-353 -35 -349 -31
-351 -32 -351 -34
-352 -33 -351 -32
839 -323 842 -313
841 -321 840 -318
841 -321 840 -318
938 -62 941 -58
940 -61 939 -60
940 -61 939 -60
-702 416 -699 423
-700 419 -700 417
-700 419 -700 417
-337 349 -332 353
-333 351 -333 350...

output:

0.0000000000
2.5000000000
30.0000000000
12.0000000000
21.0000000000
10.0000000000
9.0000000000
1.5000000000
7.0000000000
0.0000000000
18.0000000000
36.0000000000
24.0000000000
9.0000000000
5.0000000000
0.0000000000
21.0000000000
30.0000000000
12.0000000000
9.5000000000
0.0000000000
20.0000000000
10....

result:

ok 100000 numbers

Test #22:

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

input:

100000
-537 167 -533 182
-534 180 -534 173
-534 176 -534 180
-165 -532 -131 -523
-161 -525 -157 -524
-157 -524 -161 -525
899 556 904 564
901 560 900 561
900 561 902 559
-931 542 -914 549
-930 543 -926 543
-930 543 -918 543
807 -892 816 -876
815 -885 814 -881
815 -885 814 -881
597 -596 606 -579
600 -...

output:

24.0000000000
306.0000000000
17.5000000000
35.0000000000
144.0000000000
153.0000000000
52.0000000000
0.0000000000
0.0000000000
36.0000000000
56.0000000000
4.3750000000
0.0000000000
172.0000000000
20.0000000000
0.0000000000
161.0000000000
40.0000000000
98.8500000000
11.7166666667
112.0000000000
56.00...

result:

ok 100000 numbers

Test #23:

score: 0
Accepted
time: 226ms
memory: 3800kb

input:

100000
-162 86 -148 92
-154 87 -150 91
-160 91 -154 87
160 -125 167 -121
161 -122 165 -124
161 -122 164 -122
-635 366 -618 382
-620 374 -622 378
-623 380 -621 376
615 -689 632 -668
631 -676 621 -680
631 -676 621 -680
-278 61 -273 87
-277 69 -275 84
-275 84 -277 69
289 534 301 547
299 545 292 544
299...

output:

0.8333333333
2.0000000000
42.5000000000
357.0000000000
130.0000000000
156.0000000000
33.0000000000
17.3785714286
154.0000000000
36.0000000000
24.0000000000
32.0000000000
0.0000000000
8.0416666666
506.0000000000
0.0000000000
177.8967391304
26.6666666667
434.0000000000
742.0000000000
109.3750000000
3....

result:

ok 100000 numbers

Test #24:

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

input:

100000
-27 318 2 328
-3 320 -23 326
-23 326 -3 320
444 632 486 691
484 638 458 686
471 662 484 638
-630 909 -627 954
-628 912 -629 918
-629 918 -628 912
-393 509 -389 559
-390 532 -390 510
-390 532 -390 510
945 -907 964 -866
952 -869 951 -896
949 -875 956 -877
272 584 286 615
276 599 273 602
276 599...

output:

290.0000000000
1123.5000000000
135.0000000000
200.0000000000
0.0000000000
218.6666666667
0.0000000000
400.0000000000
0.0000000000
2275.0000000000
1152.0000000000
54.0000000000
169.7631578947
167.1428571429
34.0000000000
2.6250000000
0.0000000000
2480.0000000000
0.0000000000
396.0000000000
2262.00000...

result:

ok 100000 numbers

Test #25:

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

input:

100000
-48 216 12 300
-42 226 2 269
2 269 -42 226
449 -897 523 -671
511 -707 503 -724
452 -743 495 -741
-132 -959 -58 -943
-83 -948 -113 -947
-69 -956 -113 -947
199 -522 296 -129
228 -308 255 -426
255 -426 228 -308
337 -855 388 -818
355 -852 366 -840
366 -840 355 -852
727 712 924 817
736 814 795 773...

output:

5040.0000000000
0.0000000000
289.5393939394
38121.0000000000
1887.0000000000
0.0000000000
3160.0000000000
204.5000000000
0.0000000000
20114.0000000000
0.0000000000
814.0000000000
397.4016666667
13585.7142857143
0.0000000000
217.6923076923
242.8571428571
0.0000000000
57528.0000000000
307.7954545455
2...

result:

ok 100000 numbers

Test #26:

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

input:

100000
69 -124 92 -99
90 -103 89 -117
90 -103 89 -117
569 -330 587 -111
572 -194 580 -119
572 -194 580 -119
457 468 830 914
753 680 621 606
489 532 621 606
462 -15 551 70
521 -1 506 -1
504 -1 476 -1
-29 152 111 582
3 254 -1 441
34 335 36 484
-367 -578 -362 -150
-364 -245 -365 -458
-365 -458 -364 -24...

output:

575.0000000000
3942.0000000000
0.0000000000
0.0000000000
0.0000000000
2140.0000000000
21010.0000000000
18444.0000000000
28665.0000000000
0.0000000000
14000.0000000001
3336.0000000000
8482.5000000000
17800.0000000000
66286.0000000000
3822.0000000000
55552.0000000000
18285.0000000000
96.0000000000
134...

result:

ok 100000 numbers

Test #27:

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

input:

100000
-935 -289 -491 868
-614 -6 -860 344
-860 344 -614 -6
-283 -623 420 999
-36 -349 -80 -442
-124 -535 8 -256
-378 -817 55 914
-127 -314 -37 633
-127 -314 -37 633
-249 -550 754 889
509 -515 287 62
509 -515 65 639
-987 -629 887 286
810 -560 301 -383
301 -383 810 -560
-836 -839 132 745
-661 -812 -2...

output:

513708.0000000001
76751.2892228739
749523.0000000000
600522.3483535527
1714710.0000000000
1533312.0000000000
0.0000000000
0.0000000000
0.0000000000
100436.0000000000
430802.4524714829
0.0000000000
594520.0000000000
1225296.0000000000
1088724.0000000000
0.0000000000
1184592.0000000000
504000.00000000...

result:

ok 100000 numbers

Test #28:

score: 0
Accepted
time: 237ms
memory: 3896kb

input:

100000
-967 -986 989 976
60 -380 -347 453
60 -380 -347 453
-943 -995 933 978
887 410 -500 -140
887 410 -500 -140
-870 -835 977 994
181 -581 823 -821
823 -821 181 -581
-985 -832 772 915
-551 402 214 884
-551 402 214 884
-969 -820 988 965
478 326 551 34
420 558 551 34
-988 -344 997 877
-942 -184 -881 ...

output:

3837672.0000000000
3701348.0000000000
3378163.0000000005
3069479.0000000000
2013508.3750000000
2423685.0000000000
0.0000000000
91400.5797173567
3743904.0000000000
700867.6977178832
370580.4588690780
0.0000000001
106662.2153029381
0.0000000000
3922368.0000000000
333909.2257925025
3710304.0000000000
1...

result:

ok 100000 numbers

Test #29:

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

input:

100000
-992 -991 993 999
-287 723 -688 -530
-688 -530 -287 723
-999 -1000 1000 1000
-841 -413 137 359
626 745 -352 -27
-997 -1000 997 986
-77 222 -133 959
-133 959 -77 222
-1000 -996 998 978
616 432 793 -930
616 432 793 -930
-1000 -994 977 965
776 -646 970 690
873 22 970 690
-973 -982 993 999
-796 8...

output:

3950150.0000000000
1542553.8451900356
3960083.9999999995
3944052.0000000000
1610389.3226047901
3894646.0000000000
3830324.0000000000
1834613.2144702843
256920.0868967181
0.0000000000
0.0000000000
3986006.0000000000
3990000.0000000000
0.0000000000
0.0000000000
3874290.0000000000
3876880.0000000000
14...

result:

ok 100000 numbers

Test #30:

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

input:

100000
757 -469 768 -466
763 -467 759 -468
759 -468 763 -467
-860 -809 -842 -799
-859 -802 -849 -804
-854 -803 -844 -805
-580 -402 -576 -398
-579 -400 -579 -399
-577 -399 -579 -400
-615 364 -599 375
-605 368 -607 373
-605 368 -607 373
141 -198 160 -187
146 -193 150 -190
142 -196 146 -193
-521 -135 -...

output:

33.0000000000
52.0000000000
3.0000000000
176.0000000000
0.0000000000
20.6333333333
35.0000000000
5.0000000000
12.0000000000
12.0000000000
90.0000000000
44.0000000000
12.0000000000
48.0000000000
15.9500000000
19.4166666667
156.0000000000
0.0000000000
0.0000000000
6.0000000000
10.0000000000
40.0000000...

result:

ok 100000 numbers

Test #31:

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

input:

100000
24 -943 45 -937
33 -939 31 -940
31 -940 29 -941
24 -407 47 -374
26 -397 40 -382
30 -405 26 -397
-338 -401 -335 -398
-337 -399 -336 -399
-337 -399 -336 -399
-186 554 -141 558
-151 555 -176 556
-151 555 -176 556
-624 109 -617 177
-621 175 -620 157
-622 137 -619 139
-930 -172 -903 -158
-911 -161...

output:

0.0000000000
2.8666666667
9.0000000000
180.0000000000
0.0000000000
154.0000000000
0.0000000000
263.5000000000
238.0000000000
374.0000000000
1242.9583333333
23.9807692308
144.0000000000
0.0000000000
0.0000000000
551.0000000000
0.0000000000
81.0000000000
310.0000000000
15.0000000000
42.0000000000
96.0...

result:

ok 100000 numbers

Test #32:

score: 0
Accepted
time: 224ms
memory: 3820kb

input:

100000
-907 -546 -898 -457
-902 -502 -901 -463
-902 -502 -901 -463
-366 -693 -359 -646
-363 -663 -364 -665
-361 -659 -364 -665
373 -119 390 -110
378 -111 385 -111
376 -111 388 -111
-737 -682 -720 -679
-728 -680 -729 -680
-727 -681 -729 -680
695 214 731 263
723 247 700 218
711 219 709 250
482 -243 48...

output:

801.0000000000
208.2500000000
63.0000000000
23.0000000000
0.0000000000
84.0000000000
810.0000000000
0.0000000000
1860.0000000000
1656.0000000000
56.0000000000
204.0000000000
290.0000000000
1010.0000000000
13.5208333333
156.0000000000
867.0000000000
2950.0000000000
18.0000000000
0.0000000000
282.0000...

result:

ok 100000 numbers

Test #33:

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

input:

100000
-737 590 -688 597
-732 595 -731 596
-732 595 -736 591
24 -730 52 -476
35 -564 34 -652
35 -564 34 -652
480 -273 562 -155
530 -248 511 -272
530 -248 549 -224
-370 -155 -355 -22
-368 -152 -364 -46
-364 -76 -367 -23
430 827 489 899
454 840 432 869
432 869 473 847
-310 -126 -179 -27
-204 -36 -281 ...

output:

0.0000000000
7112.0000000000
0.0000000000
0.0000000000
302.9806560134
12969.0000000000
3645.0000000000
132.0000000000
5.9548611111
29016.0000000000
0.0000000000
31987.5937500000
5022.0000000000
112.5590558091
0.0000000000
1.1250000000
5349.1750000000
7920.0000000000
0.0000000000
1360.6446644664
475....

result:

ok 100000 numbers

Test #34:

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

input:

100000
-717 -894 -455 -770
-597 -886 -533 -836
-533 -836 -565 -861
-798 -326 -742 75
-782 -234 -759 -35
-782 -234 -759 -35
113 -696 295 -596
277 -641 217 -650
117 -665 177 -656
280 -873 734 -751
733 -843 427 -863
344 -796 427 -863
-685 -613 -543 -590
-598 -601 -596 -612
-596 -612 -567 -595
734 309 9...

output:

16449.3750000000
22456.0000000000
0.0000000000
43.6294196394
3.0431034483
872.3473214286
39611.0000000000
17.0454545454
0.0000000000
5594.5753575358
0.0000000000
36295.7241379310
7812.0000000000
15811.0000000000
0.0000000000
0.0000000000
38318.9950142450
0.0000000000
0.0000000000
3822.8750000000
228...

result:

ok 100000 numbers

Test #35:

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

input:

100000
-935 -968 975 962
310 93 414 637
219 -383 115 -927
-998 -975 937 981
390 157 -401 -464
390 157 -401 -464
-995 -419 994 865
-281 846 -197 -136
-197 -136 -239 355
-975 -964 998 941
-576 -35 -328 781
-359 679 -328 781
-983 -938 927 845
159 -827 528 481
282 -391 405 45
-982 -967 951 970
804 -685 ...

output:

0.0000000000
3784859.9999999995
1580064.0305498983
739091.6029411765
899036.1238532111
66224.3522570120
0.0000000000
3430916.0000000000
2071579.1807432431
245252.3099778433
643532.4271844662
3323293.0000000000
3347344.0000000000
0.0000000000
0.0000000000
4229.3810750820
2317345.0000000000
0.00000000...

result:

ok 100000 numbers