QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#188911#4886. Best SunDualqwqAC ✓1745ms9196kbC++237.0kb2023-09-26 16:33:082023-09-26 16:33:09

Judging History

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

  • [2023-09-26 16:33:09]
  • 评测
  • 测评结果:AC
  • 用时:1745ms
  • 内存:9196kb
  • [2023-09-26 16:33:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e2 + 5;
typedef long long i64;
typedef double db;
typedef pair<int,int> pii;
#define FI first
#define SE second
const db eps = 1e-9,PI = acos(-1.0);
mt19937 Rnd(1919810);
struct Vec {
	int x,y;
	Vec(){}
	Vec(const int _x,const int _y):x(_x),y(_y){}
	inline Vec operator + (const Vec &rhs) const { return Vec(x + rhs.x,y + rhs.y);}
	inline Vec operator - (const Vec &rhs) const { return Vec(x - rhs.x,y - rhs.y);}
	inline i64 operator * (const Vec &rhs) const { return 1ll * x * rhs.y - 1ll * y * rhs.x;}
	inline bool operator == (const Vec &rhs) const { return x == rhs.x && y == rhs.y;}
};
Vec O(0,0);
inline bool Cmp(const Vec &x,const Vec &y) { return (x.y == y.y) ? (x.x < y.x) : (x.y < y.y);}
inline i64 Dot(const Vec &A,const Vec &B) { return 1ll * A.x * B.x + 1ll * A.y * B.y;}
inline db Distance(const Vec &A,const Vec &B) { return sqrt(Dot(A - B,A - B));}
inline db Area(const Vec &A,const Vec &B,const Vec &C) { return 0.5 * abs(A * B + B * C + C * A);}
inline bool Equal(const db &A,const db &B) { return fabs(A - B) < eps;}
inline bool InSegment(const Vec &A,const Vec &B,const Vec &p) { return Equal(Distance(A,p) + Distance(p,B),Distance(A,B));}
inline bool InTriangle(const Vec &A,const Vec &B,const Vec &C,const Vec &p) {
	if((B - A) * (p - A) >= 0 && (C - B) * (p - B) >= 0 && (A - C) * (p - C) >= 0) return true;
	if((B - A) * (p - A) <= 0 && (C - B) * (p - B) <= 0 && (A - C) * (p - C) <= 0) return true;
	return false;
	// return Area(A,B,p) + Area(B,C,p) + Area(C,A,p) == Area(A,B,C);
}
inline Vec Rotate(const Vec &A) { return Vec(-A.y,A.x);}
inline int sgn(const Vec &A) { return A.y > 0 || A.y == 0 && A.x > 0;}
Vec p[N];
int n;
int V[N][N],VL[N][N]; 
int TagO;
db sum[N][N];
inline int NeedAdd(const Vec &A,const Vec &B,const Vec &p) {
	if(!InTriangle(O,A,B,p)) return 0;
	if(!p.x && !p.y) return 0;
	// if(InSegment(A,B,p)) return 0;
	if((O - p) * (A - p) == 0 
		|| (O - p) * (B - p) == 0 || (A - p) * (B - p) == 0) return 1;
	return 2;
}
inline bool CheckTriangle(int i,int j,int k) {
	
	if(InSegment(p[i],p[j],p[k])) return VL[i][j] <= 1;
	if(InSegment(p[i],p[k],p[j])) return VL[i][k] <= 1;
	if(InSegment(p[j],p[k],p[i])) return VL[j][k] <= 1;
	int tmp = TagO - (p[i] == O) - (p[j] == O) - (p[k] == O);
	if(tmp && InTriangle(p[i],p[j],p[k],O)) return false;
	if(VL[i][j] || VL[j][k] || VL[i][k]) return false;
	// if(i == 1 && j == 1 && k == 4) puts("done");
	int num = 0;
	int v1 = V[i][j] - NeedAdd(p[i],p[j],p[k]);
	int v2 = V[j][k] - NeedAdd(p[j],p[k],p[i]);
	int v3 = V[k][i] - NeedAdd(p[k],p[i],p[j]);
	if(p[i] * p[j] > 0) num += v1; else if(p[i] * p[j] < 0) num -= v1;
	if(p[j] * p[k] > 0) num += v2; else if(p[j] * p[k] < 0) num -= v2;
	if(p[k] * p[i] > 0) num += v3; else if(p[k] * p[i] < 0) num -= v3;
	// 上面没有计算 Op[i],Op[j],Op[k] 三条线的结果

	// int brt = 0;
	// for(int t = 1;t <= n;t++)
	// 	if(i != t && j != t && k != t && InTriangle(p[i],p[j],p[k],p[t])) ++brt;
	// if((abs(num) > 0) ^ (brt > 0)) {
	// 	printf("%d %d %d\n",i,j,k);
	// 	printf("p[%d]:%d,%d\n",1,p[1].x,p[1].y);
	// 	printf("p[%d]:%d,%d\n",2,p[2].x,p[2].y);
	// 	printf("p[%d]:%d,%d\n",3,p[3].x,p[3].y);
	// 	printf("p[%d]:%d,%d\n",4,p[4].x,p[4].y);
	// 	printf("%d %d %d\n",v1,v2,v3);
	// 	exit(2145);
	// }
	// assert(num % 2 == 0);
	// assert(abs(num) == brt);
	return num == 0;
}

struct Line {
	int s,t,type;
	Vec v;
	Line(){}
	Line(const int _s,const int _t,const int _type,const Vec _v):
		s(_s),t(_t),type(_type),v(_v){}
	inline bool operator < (const Line &rhs) const { 
		// return Angle(v) < Angle(rhs.v);
		int t1 = sgn(this->v),t2 = sgn(rhs.v);
		if(t1 != t2) return t1 > t2;
		i64 val = this->v * rhs.v;
		// db val = Angle(this->v) - Angle(rhs.v);
		if(val) return val > 0;
		else return type < rhs.type;
	}
};
Line L[N * N * 2];
int tot;
inline void Init() {
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> p[i].x >> p[i].y;
	TagO = 0;
	for(int i = 1;i <= n;i++) if(p[i] == O) TagO++;
	sort(p + 1,p + n + 1,Cmp);
	for(int i = 1;i <= n;i++) 
		for(int j = 1;j <= n;j++)
			if(i < j)
			for(int k = 1;k <= n;k++) {
				if(k == i || k == j) continue;	
				if(p[k] == O) continue;
				if(!InTriangle(p[i],O,p[j],p[k])) continue;

				// if(InSegment(O,p[i],p[k]) || (!InSegment(O,p[j],p[k]) && !InSegment(O,p[i],p[k])))
				// // if(InSegment(p[i],p[j],p[k]) || (!InSegment(O,p[i],p[k]) && !InSegment(O,p[j],p[k])))
					V[i][j] += NeedAdd(p[i],p[j],p[k]);
				if(InSegment(p[i],p[j],p[k])) ++VL[i][j];
			}
			else V[i][j] = V[j][i],VL[i][j] = VL[j][i];
	// printf("V,VL[1,2]:%d,%d\n",V[1][2],VL[1][2]);
	// printf("V,VL[3,1]:%d,%d\n",V[3][1],VL[3][1]);
	// printf("V,VL[2,3]:%d,%d\n",V[2][3],VL[2][3]);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++)
			for(int k = 1;k <= n;k++) {
				if(k == i || k == j) continue;
				if((p[k] - p[i]) * (p[j] - p[i]) <= 0) continue;
				if(Dot(p[j] - p[i],p[k] - p[i]) >= 0 && Dot(p[i] - p[j],p[k] - p[j]) > 0)
					sum[i][j] += min(Distance(p[k],p[i]),Distance(p[k],p[j]));
			}
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= n;j++) {
			if(i == j) continue;
			sum[i][j] += Distance(p[i],p[j]);
			L[++tot] = Line(i,j,0,p[j] - p[i]);
			L[++tot] = Line(i,j,1,Rotate(p[j] - p[i]));
		}
	// printf("Angle(1,2):%.6lf\n",Angle(p[2] - p[1]));
	// printf("Angle(1,3):%.6lf\n",Angle(p[3] - p[1]));
	// printf("Angle(2,1):%.6lf\n",Angle(p[1] - p[2]));
	// printf("Angle(2,3):%.6lf\n",Angle(p[3] - p[2]));
	// printf("Angle(3,1):%.6lf\n",Angle(p[1] - p[3]));
	// printf("Angle(3,2):%.6lf\n",Angle(p[2] - p[3]));

	sort(L + 1,L + tot + 1);
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}

db dp[N];
inline bool Check(int st,db mid) {
	for(int i = 1;i <= n;i++) dp[i] = -1e15;
	dp[st] = -eps;
	// printf("Check:%d\n",st);
	for(int i = 1;i <= tot;i++) {
		int s = L[i].s,t = L[i].t,tp = L[i].type;
		// printf("L:%d,%d,%d\n",s,t,tp);
		// printf("CheckTriangle[%d,%d,%d]:%d\n",st,s,t,CheckTriangle(st,s,t));
		if(tp == 1) {
			if(s >= st) dp[s] -= mid * Distance(p[s],p[t]);
		} else 
			if(s >= st && t >= st && CheckTriangle(st,s,t))
				dp[t] = max(dp[t],dp[s] + Area(p[st],p[s],p[t]) - mid * sum[s][t]); 
	}
	// for(int i = 1;i <= n;i++) printf("dp[%d]=%.12lf\n",i,dp[i]);
	return dp[st] > eps;
}
inline void Clr(int n) {
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) V[i][j] = VL[i][j] = sum[i][j] = 0;
	tot = 0;
}
inline void work() {
	Clr(n);
	Init();
	static int perm[N];
	for(int i = 1;i <= n;i++) perm[i] = i;
	shuffle(perm + 1,perm + n + 1,Rnd);
	db ans = 0;
	// printf("Check:%d\n",Check(1,0));
	for(int i = 1;i <= n;i++) 
		if(Check(perm[i],ans)) {
			db lef = ans,rig = 1e6;
			for(int _ = 1;_ <= 45;_++) {
				db mid = (lef + rig) / 2;
				if(Check(perm[i],mid)) lef = mid;
				else rig = mid;
			}
			ans = lef;
		}
	printf("%.10lf\n",ans);
	cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
int main() {
	int T;
	cin >> T;
	while(T--) work();
	return 0;
}
/*
1
4
1 -4
3 -3
1 -1
2 1
*/

詳細信息

Test #1:

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

input:

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

output:

0.3090169685
1.2368613993
0.2711375252
1.5631001995

result:

ok 4 numbers

Test #2:

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

input:

10000
3
702262 828158
-350821 -420883
-466450 13507
3
28647 -193498
126436 -864937
-287798 738936
3
270358 -269567
745815 -485408
834083 677952
3
-2036 -403634
742978 -263774
975937 -609237
3
584248 -472620
482016 -356760
284902 903881
3
-292004 504925
-935756 373793
-781101 -434659
3
-858513 684433...

output:

85789.0873983536
18268.5193616692
102489.9883902606
66685.7544280788
18674.6579373960
106468.9651319668
14427.0246510700
29966.2453025178
143547.7510835596
13097.1756881024
162410.1683169670
72070.9324178586
29369.9926278634
52867.2944310813
90314.3083467341
99775.9271965606
144449.7053083467
64406....

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 98ms
memory: 6056kb

input:

10000
3
2 2
2 -2
-5 -5
3
-3 5
5 -4
2 -2
3
-4 1
2 -2
-4 4
3
1 -4
2 1
-4 1
3
2 1
-1 1
-3 3
3
4 5
3 -1
-3 -3
3
1 5
5 0
5 -1
3
2 -3
-5 -3
5 3
3
-4 4
0 -5
5 4
3
2 -3
5 0
2 -5
3
-2 -3
5 -3
5 4
3
-1 4
4 4
4 3
3
5 3
-1 4
2 -1
3
2 -3
4 3
-4 3
3
0 4
-2 -2
-1 -3
3
-2 0
-4 -2
4 2
3
-3 -1
3 1
1 -3
3
2 -5
2 3
-4 ...

output:

0.6507006844
0.2268090498
0.4946825527
0.8255326236
0.2675324708
0.7379284455
0.1368529183
0.8277457937
1.3896280961
0.2484761410
1.0251262381
0.2252451168
0.7981688270
1.0521776233
0.2700907373
0.2210279888
0.6549291243
1.0657925316
0.1207361606
0.1727212009
0.4458825060
0.2484761410
0.1224985624
0...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 108ms
memory: 4036kb

input:

5625
4
-405394 -381883
602267 -335687
-620806 984110
271283 531233
4
196903 -993060
290851 358123
-890076 -717709
-681138 209884
4
-849589 607722
-21517 -586295
208561 -220953
924518 622983
4
-832186 456270
289934 43656
636006 339718
188963 113907
4
-305762 -872205
-520125 368722
-774548 984204
4245...

output:

232625.0042744107
268175.8269859619
159589.3236305130
60440.7530425703
133893.1234363469
63201.9907486067
167697.6634061235
129470.0132843047
126903.8540727934
106643.9712630825
131692.3112278801
100421.0550161986
148490.2748178740
68842.2423098165
241376.1911161032
303904.5464356604
77462.333614761...

result:

ok 5625 numbers

Test #5:

score: 0
Accepted
time: 133ms
memory: 6044kb

input:

5625
4
-2 -1
4 -5
-2 -4
-4 -4
4
-1 -5
4 4
2 -5
-5 1
4
-3 -4
-3 -1
-5 -1
4 -2
4
-2 4
-4 1
-1 -1
5 -4
4
-3 -5
-1 4
5 -1
3 5
4
-4 -2
1 4
-1 1
3 4
4
-5 3
-3 3
5 -4
-1 4
4
1 2
2 -5
1 0
0 -3
4
-5 -4
2 -3
5 3
-3 2
4
2 -2
-4 3
1 -4
-5 -5
4
-3 5
-2 4
1 3
1 -4
4
0 -5
5 -5
0 -2
-3 2
4
0 5
-1 -4
-2 0
4 -1
4
4 -...

output:

0.4919681942
1.6080239257
0.6764635424
0.8146821049
1.5727954005
0.2020447880
0.4423672879
0.3055831996
1.5089069052
1.3227875115
0.5218559238
0.3982804238
1.2194946066
1.1774912423
1.3951026858
1.0737731202
0.7540897691
0.6075590875
1.4373192190
0.9671123280
0.9534878387
1.4836242599
1.2273730192
0...

result:

ok 5625 numbers

Test #6:

score: 0
Accepted
time: 138ms
memory: 4092kb

input:

3600
5
114127 146710
467065 -311758
189643 449065
-303893 -215009
-789281 -140748
5
-449893 654165
-899120 -560520
719351 652759
285007 471281
987628 -767128
5
-587522 89736
-355416 -178001
801765 512722
314119 -136906
350051 762194
5
85697 920768
161507 -533920
-536515 401333
-27632 -987465
112237 ...

output:

84655.1995486339
270848.7268670296
202824.0367340314
135615.1918739256
119666.5085435029
89811.8707706889
254983.1535752974
189662.7472664882
64951.6570894377
154748.4422910088
214519.6820790192
163467.5328002302
278857.2574408529
191490.4979057995
172625.5296426240
144947.5248147898
232735.62583867...

result:

ok 3600 numbers

Test #7:

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

input:

3600
5
2 6
-6 4
4 0
-5 0
3 1
5
0 3
5 -5
2 6
4 0
2 -4
5
2 -2
-6 -3
-5 -5
-1 3
-4 0
5
0 6
-3 -5
5 1
4 -3
-5 6
5
0 -6
-6 -5
-2 6
1 6
2 0
5
2 1
6 5
4 -1
-3 -2
-6 4
5
-1 -2
5 -6
-1 4
-2 3
6 4
5
-6 3
6 -5
4 -4
3 -1
2 -6
5
5 -4
1 -5
1 0
5 -1
3 2
5
-4 6
2 -4
1 -4
5 5
-1 6
5
-3 0
0 6
-2 5
-5 5
2 6
5
2 -1
-4 ...

output:

1.3917338047
1.0600076621
1.3386604733
2.1786414884
1.8677635181
1.2550644197
1.8197054398
0.9463023056
1.1316433017
1.5772390611
0.5212123999
1.5371795538
0.9473384575
1.0470909720
0.5572297823
1.2085970170
1.2302893664
0.6675741417
0.3665059865
0.6943425277
0.5121414176
0.4362963750
0.8610973339
0...

result:

ok 3600 numbers

Test #8:

score: 0
Accepted
time: 133ms
memory: 3904kb

input:

3600
5
-3 1
0 -1
2 -3
4 1
5 0
5
-3 -5
1 -5
-2 -2
3 2
1 5
5
-4 -2
4 5
5 3
2 -4
-4 0
5
0 4
-5 3
1 4
-1 1
4 1
5
5 -3
2 -5
-3 -4
-1 1
5 1
5
-5 5
-2 1
-3 2
2 2
-4 5
5
-2 -3
-1 3
1 1
3 -2
-2 -2
5
2 1
-2 -3
-3 -3
5 0
-5 4
5
2 2
-2 5
5 -1
4 -5
-2 4
5
-4 5
-1 -3
-2 5
5 -1
-4 3
5
-5 -4
-1 -3
0 -1
-5 1
-4 -3
5...

output:

0.5433808490
1.2079312626
1.5754945621
0.8075181303
1.5566795740
0.6824490662
0.9074401042
0.9508389961
0.8537708709
1.3713082012
0.7426407751
0.4014915969
0.7474276060
0.4934691483
0.7112144829
0.6092998319
1.2344361488
0.4338148128
1.4679333256
0.6954624325
0.6914801531
0.8433199768
1.1987088726
1...

result:

ok 3600 numbers

Test #9:

score: 0
Accepted
time: 140ms
memory: 6116kb

input:

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

output:

2.1052009095
1.5367686501
1.6070202283
3.5263473168
1.9784334680
1.0825185755
0.9461632076
1.6023271075
2.8837721402
0.9408148756
1.7013625613
1.6009202205
1.9334872323
0.6918659586
1.8339842711
0.6306479407
3.4339518703
2.4487067378
1.5516660596
1.1454890149
0.8735166647
1.5938651359
1.4443102714
2...

result:

ok 3600 numbers

Test #10:

score: 0
Accepted
time: 200ms
memory: 6120kb

input:

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

output:

2.6060274775
1.2633417725
1.1838990914
0.8827284671
1.8782272719
1.5698135706
1.5532952985
1.6328323301
1.5737994762
0.9970959561
0.9424829844
1.4172826182
1.4017665495
1.6939866361
2.8628778352
2.0553597643
2.2087768437
1.3202393648
1.5058644707
1.5958000817
1.9530554880
1.1865717598
1.0563282563
2...

result:

ok 900 numbers

Test #11:

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

input:

900
10
670067 394291
-797310 -637136
-435933 -923795
120936 309795
-934569 -688829
950758 634654
983083 900196
174829 181896
-191047 177910
258020 672165
10
424046 -657491
391198 -14995
-302986 -597011
-96387 -486090
-164032 -356501
-891789 12548
-703186 -924511
808215 -212606
659523 490088
738901 5...

output:

81290.1618383761
91483.7331961411
100154.0270558422
192606.4148202983
177441.6474344105
76150.8923721573
177358.7053738632
230115.8792668067
280209.2628450188
61218.5430212702
137504.7916377219
168344.5440410816
162167.1818149082
133102.5292692251
177087.4563457221
163543.6097759946
184494.309868969...

result:

ok 900 numbers

Test #12:

score: 0
Accepted
time: 271ms
memory: 4188kb

input:

225
20
-4 -9
-5 3
7 -10
10 7
2 7
1 4
2 2
-5 -1
-9 -1
-3 10
-8 -6
0 -5
7 -4
-6 -8
-7 -5
-1 -7
-1 -3
8 -6
6 3
8 2
20
8 2
6 -8
-3 -6
-2 9
5 -2
0 8
8 0
-7 -9
3 1
4 -10
4 7
-6 -1
-8 -7
2 -8
-8 -1
1 -9
2 -10
1 2
-7 8
-10 3
20
5 8
0 -3
9 -9
-10 -4
-10 -2
9 10
-2 8
-6 -10
6 -6
-3 7
5 10
7 7
-5 -6
-2 3
-4 0
...

output:

0.6127869848
1.1137907182
0.7615364126
1.3308058885
0.7540492120
1.3328379607
0.6703147809
1.0353127837
0.9068174078
0.9769666614
0.7502848865
0.7780315596
0.7179049112
0.5715802085
0.7721060853
0.7692910081
1.8904459886
0.8600960487
1.0777332318
1.3129810811
0.8016468248
0.8696199191
0.8573236530
1...

result:

ok 225 numbers

Test #13:

score: 0
Accepted
time: 280ms
memory: 4192kb

input:

225
20
983700 -466859
-20884 -364855
807044 -308568
-785298 910840
-61173 -276993
-872226 -878552
-235162 831941
978289 938037
585612 -598517
545857 403231
-450887 -558997
-293044 -675226
-900628 102932
-836719 -530135
-534412 -681687
-487340 -227869
161252 -557533
397943 464720
170537 68556
413322 ...

output:

103902.0526005441
185063.0384573450
60443.6573723248
118360.3646096438
157018.7851307629
103511.4658062259
65549.6994792792
67043.3588288711
105010.2705326675
93450.0576684343
96005.2282075878
54350.0986013002
134718.5353431164
98397.3545701079
71213.2949663550
77465.3939447420
75212.0930407925
1236...

result:

ok 225 numbers

Test #14:

score: 0
Accepted
time: 79ms
memory: 4400kb

input:

6
50
-107573 -479674
-523931 117259
705403 519626
-802569 -162243
510741 876735
206326 -333274
448335 -276206
482965 -837837
873180 -965235
-359525 608790
-53827 782310
689038 -718590
739597 111296
420387 -953079
-492679 -243600
-929509 1174
800731 -968797
208236 193620
249265 499134
848153 771472
5...

output:

20480.3828539945
21190.0221497536
27821.6725958609
28113.3193405147
27223.9676079317
31857.8357100237

result:

ok 6 numbers

Test #15:

score: 0
Accepted
time: 379ms
memory: 4412kb

input:

36
50
569818 -279771
972561 928848
383 744221
-453534 -154445
293032 502859
744851 436690
293077 503053
657 744258
317135 -276665
293067 502799
277103 -439313
282010 -387735
276848 -439025
972274 928763
-110443 -507380
744799 436605
282061 -387926
-453689 -154326
317468 -276534
-453630 -154510
28193...

output:

81019.4274543921
77527.2587729629
55029.2464233119
42253.1543856355
72715.8578229821
197374.6307406388
37469.7225819169
66130.3529953631
54454.5978064967
125611.0883685123
71800.2062730490
87529.3367687952
143932.8876147661
95010.1346814902
86801.3479384900
106229.4888661041
99367.3086457716
93764.6...

result:

ok 36 numbers

Test #16:

score: 0
Accepted
time: 349ms
memory: 4396kb

input:

36
50
-767165 583573
-284890 -681002
-423448 -259226
-285077 -680913
-921552 -557651
-767105 583853
-423314 -259380
790075 -225214
-921537 -557431
-767305 583770
-767124 583508
-921629 -557448
-423530 -259463
-284954 -680837
-423426 -259294
-423469 -259099
-767302 583744
-921772 -557672
-423503 -259...

output:

36643.6054805936
73491.0580576342
355454.4402131349
76283.4915153242
114070.2207770458
102751.9423399158
346834.5085962089
142611.0579378523
246800.0671139018
131055.8866665811
22279.8879892140
215589.6576250780
83424.8688141581
51800.2345429414
43278.8616878964
278223.4837556020
81405.2167205066
25...

result:

ok 36 numbers

Test #17:

score: 0
Accepted
time: 353ms
memory: 4396kb

input:

36
50
-757926 470127
-757550 470454
250422 -395772
250548 -395869
568164 -704082
250417 -396082
-757845 470427
444672 170989
250387 -395875
250484 -395866
568177 -704202
-757558 470484
250530 -395763
250488 -395883
-757754 470201
250529 -396062
-757760 470255
568050 -704413
444991 171218
444963 1710...

output:

41461.4157312312
61470.3459020843
198910.9999673769
35019.3686454291
139342.5797078109
26339.6628390343
247086.6792489548
108103.8329786103
269038.9700572530
40491.2267640828
99838.8739582890
174035.1497371408
172811.2119707150
155604.8803016135
30013.6705970499
250614.3951947112
84144.5624718379
20...

result:

ok 36 numbers

Test #18:

score: 0
Accepted
time: 473ms
memory: 4940kb

input:

9
100
-79487 826724
571284 354748
-312616 727781
-838024 249391
-79475 826592
796988 -514208
-847898 -839919
584481 896431
-847899 -839656
-312680 727782
22798 138363
466409 -215121
-36729 -925283
677267 -733543
-789119 581936
-789111 581860
271104 629366
571356 354824
-946155 -832752
571238 354954
...

output:

23149.7505948995
20131.1691208430
50752.3036752972
22743.2512424825
21418.0199422366
24609.1329750448
20676.5752705816
23043.7559151699
35012.2203029409

result:

ok 9 numbers

Test #19:

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

input:

1
10
2 -999
3 -998
4 -995
5 -990
6 -983
7 -974
8 -963
9 -950
1000 1000
-1000 1000

output:

293.8271086913

result:

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

Test #20:

score: 0
Accepted
time: 1299ms
memory: 9132kb

input:

1
300
-1000000 700000
-999999 697990
-999998 695960
-999997 693910
-999996 691840
-999995 689750
-999994 687640
-999993 685510
-999992 683360
-999991 681190
-999990 679000
-999989 676790
-999988 674560
-999987 672310
-999986 670040
-999985 667750
-999984 665440
-999983 663110
-999982 660760
-999981 ...

output:

46.7179453520

result:

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

Test #21:

score: 0
Accepted
time: 1094ms
memory: 9148kb

input:

1
300
-9999 -2
-9998 -3
-9995 -4
-9990 -5
-9983 -6
-9974 -7
-9963 -8
-9950 -9
-9935 -10
-9918 -11
-9899 -12
-9878 -13
-9855 -14
-9830 -15
-9803 -16
-9774 -17
-9743 -18
-9710 -19
-9675 -20
-9638 -21
-9599 -22
-9558 -23
-9515 -24
-9470 -25
-9423 -26
-9374 -27
-9323 -28
-9270 -29
-9215 -30
-9158 -31
-9...

output:

2367.6921379694

result:

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

Test #22:

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

input:

1
300
700000 1000000
697990 999999
695960 999998
693910 999997
691840 999996
689750 999995
687640 999994
685510 999993
683360 999992
681190 999991
679000 999990
676790 999989
674560 999988
672310 999987
670040 999986
667750 999985
665440 999984
663110 999983
660760 999982
658390 999981
656000 999980...

output:

46.7179453565

result:

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

Test #23:

score: 0
Accepted
time: 1210ms
memory: 9056kb

input:

1
300
-2 9999
-3 9998
-4 9995
-5 9990
-6 9983
-7 9974
-8 9963
-9 9950
-10 9935
-11 9918
-12 9899
-13 9878
-14 9855
-15 9830
-16 9803
-17 9774
-18 9743
-19 9710
-20 9675
-21 9638
-22 9599
-23 9558
-24 9515
-25 9470
-26 9423
-27 9374
-28 9323
-29 9270
-30 9215
-31 9158
-32 9099
-33 9038
-34 8975
-35 8...

output:

2367.6921379535

result:

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

Test #24:

score: 0
Accepted
time: 1285ms
memory: 9092kb

input:

1
300
1000000 -700000
999999 -697990
999998 -695960
999997 -693910
999996 -691840
999995 -689750
999994 -687640
999993 -685510
999992 -683360
999991 -681190
999990 -679000
999989 -676790
999988 -674560
999987 -672310
999986 -670040
999985 -667750
999984 -665440
999983 -663110
999982 -660760
999981 -...

output:

46.7179453488

result:

ok found '46.7179453', expected '46.7179454', error '0.0000000'

Test #25:

score: 0
Accepted
time: 1174ms
memory: 9088kb

input:

1
300
9999 2
9998 3
9995 4
9990 5
9983 6
9974 7
9963 8
9950 9
9935 10
9918 11
9899 12
9878 13
9855 14
9830 15
9803 16
9774 17
9743 18
9710 19
9675 20
9638 21
9599 22
9558 23
9515 24
9470 25
9423 26
9374 27
9323 28
9270 29
9215 30
9158 31
9099 32
9038 33
8975 34
8910 35
8843 36
8774 37
8703 38
8630 3...

output:

2367.6921379601

result:

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

Test #26:

score: 0
Accepted
time: 709ms
memory: 9008kb

input:

1
300
-700000 -1000000
-697990 -999999
-695960 -999998
-693910 -999997
-691840 -999996
-689750 -999995
-687640 -999994
-685510 -999993
-683360 -999992
-681190 -999991
-679000 -999990
-676790 -999989
-674560 -999988
-672310 -999987
-670040 -999986
-667750 -999985
-665440 -999984
-663110 -999983
-6607...

output:

46.7179453508

result:

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

Test #27:

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

input:

1
300
2 -999999
3 -999998
4 -999995
5 -999990
6 -999983
7 -999974
8 -999963
9 -999950
10 -999935
11 -999918
12 -999899
13 -999878
14 -999855
15 -999830
16 -999803
17 -999774
18 -999743
19 -999710
20 -999675
21 -999638
22 -999599
23 -999558
24 -999515
25 -999470
26 -999423
27 -999374
28 -999323
29 -9...

output:

24.9160640993

result:

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

Test #28:

score: 0
Accepted
time: 1053ms
memory: 9000kb

input:

1
300
2 -44999
3 -44998
4 -44995
5 -44990
6 -44983
7 -44974
8 -44963
9 -44950
10 -44935
11 -44918
12 -44899
13 -44878
14 -44855
15 -44830
16 -44803
17 -44774
18 -44743
19 -44710
20 -44675
21 -44638
22 -44599
23 -44558
24 -44515
25 -44470
26 -44423
27 -44374
28 -44323
29 -44270
30 -44215
31 -44158
32...

output:

479.3020660438

result:

ok found '479.3020660', expected '479.3020661', error '0.0000000'

Test #29:

score: 0
Accepted
time: 1200ms
memory: 9008kb

input:

1
300
2 -9999
3 -9998
4 -9995
5 -9990
6 -9983
7 -9974
8 -9963
9 -9950
10 -9935
11 -9918
12 -9899
13 -9878
14 -9855
15 -9830
16 -9803
17 -9774
18 -9743
19 -9710
20 -9675
21 -9638
22 -9599
23 -9558
24 -9515
25 -9470
26 -9423
27 -9374
28 -9323
29 -9270
30 -9215
31 -9158
32 -9099
33 -9038
34 -8975
35 -8...

output:

2367.6921379652

result:

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

Test #30:

score: 0
Accepted
time: 1175ms
memory: 9136kb

input:

1
300
2 -49999
3 -49998
4 -49995
5 -49990
6 -49983
7 -49974
8 -49963
9 -49950
10 -49935
11 -49918
12 -49899
13 -49878
14 -49855
15 -49830
16 -49803
17 -49774
18 -49743
19 -49710
20 -49675
21 -49638
22 -49599
23 -49558
24 -49515
25 -49470
26 -49423
27 -49374
28 -49323
29 -49270
30 -49215
31 -49158
32...

output:

7347.5787737187

result:

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

Test #31:

score: 0
Accepted
time: 1193ms
memory: 9012kb

input:

1
300
2 -99999
3 -99998
4 -99995
5 -99990
6 -99983
7 -99974
8 -99963
9 -99950
10 -99935
11 -99918
12 -99899
13 -99878
14 -99855
15 -99830
16 -99803
17 -99774
18 -99743
19 -99710
20 -99675
21 -99638
22 -99599
23 -99558
24 -99515
25 -99470
26 -99423
27 -99374
28 -99323
29 -99270
30 -99215
31 -99158
32...

output:

7264.8235486766

result:

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

Test #32:

score: 0
Accepted
time: 787ms
memory: 8960kb

input:

1
300
2 -999999
3 -999998
4 -999995
5 -999990
6 -999983
7 -999974
8 -999963
9 -999950
10 -999935
11 -999918
12 -999899
13 -999878
14 -999855
15 -999830
16 -999803
17 -999774
18 -999743
19 -999710
20 -999675
21 -999638
22 -999599
23 -999558
24 -999515
25 -999470
26 -999423
27 -999374
28 -999323
29 -9...

output:

80244.5137404414

result:

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

Test #33:

score: 0
Accepted
time: 1745ms
memory: 9140kb

input:

1
300
-582688 -338066
65950 664506
726195 -342195
778617 -357210
-854288 556277
300499 294357
643715 884595
145808 699895
823594 197029
-326906 -938477
-635849 -984773
-133686 656789
-435448 690719
903384 -472986
82595 315750
-162788 541714
-77694 -237304
-850565 -426412
248922 -808508
-719332 -6663...

output:

1478.8300558656

result:

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

Test #34:

score: 0
Accepted
time: 1427ms
memory: 9144kb

input:

1
300
329399 -774056
-453420 -971922
-963389 -692906
-901061 -690960
-954671 -555749
954332 -856245
97920 127454
422794 -72309
402518 -482396
-274243 -242236
-63992 224700
841180 586025
-266496 -824730
-178245 -230280
680876 907784
553835 674598
89593 396532
143208 -684880
538608 -578116
-422477 757...

output:

972.4232802278

result:

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

Test #35:

score: 0
Accepted
time: 1335ms
memory: 9108kb

input:

1
300
-360611 262745
-266788 208188
-959303 -907228
-443316 -204307
682906 -640611
-629502 -217089
-323067 -687634
437059 491032
-924621 882842
844758 667473
765630 -661241
-192156 -841346
-154832 -812793
-47327 10282
-597348 957691
892586 942751
142330 937555
953415 -727776
-605831 643868
-310790 -...

output:

1247.6354475703

result:

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

Test #36:

score: 0
Accepted
time: 1348ms
memory: 9088kb

input:

1
300
-206748 733504
405233 346961
-313290 -216319
-485737 -231831
-164104 165946
-515020 -589364
982156 -80607
873259 619605
-482416 -888108
-569548 252891
-445640 901994
985477 -967333
42455 -483916
73904 760015
-943641 942808
396828 484027
-841584 -24224
-175993 952815
790566 541282
-279849 -3442...

output:

999.0193963582

result:

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

Test #37:

score: 0
Accepted
time: 1500ms
memory: 9140kb

input:

1
300
580502 -850604
-828356 778
184624 -535893
-697221 -969976
896503 -655248
-76966 -243055
60920 160544
44843 -658551
-447963 886466
278568 389553
-623912 -127161
678049 -413324
-430351 -318993
-817724 -933164
-711215 340590
-74113 689203
68654 -100261
182253 786353
970301 867792
-749733 -811174
...

output:

842.0590723713

result:

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

Test #38:

score: 0
Accepted
time: 1476ms
memory: 9196kb

input:

1
300
-316120 -118763
45309 190875
409669 -105265
-506284 573308
-516833 322648
-866719 -936225
-12677 -985703
711314 569209
941787 83443
-514860 686132
-790586 -545380
430362 -424821
-833415 938854
-942534 683223
-240135 606924
-403050 269157
-215947 985881
-549116 600378
459464 -595098
725250 1147...

output:

1024.4978698409

result:

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

Test #39:

score: 0
Accepted
time: 1187ms
memory: 9148kb

input:

1
300
-173407 -202877
781435 -868900
-708456 340380
-576940 717700
182725 270819
936854 705842
-558936 563953
-442817 -537862
456021 536960
-280357 -280460
865334 142839
774139 179758
441597 150328
97859 -980348
-33644 644740
-930102 492073
-672777 225390
567301 -123428
272474 613299
939529 -568972
...

output:

999.8589008248

result:

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

Test #40:

score: 0
Accepted
time: 1665ms
memory: 9032kb

input:

1
300
-345250 -831776
-186776 -708481
-461210 345548
-813591 339981
875529 -243454
-612714 -565349
342248 -74704
440632 -335722
-680195 541251
-40910 -905178
644877 899186
274573 743026
873540 -442740
535392 952686
797733 860447
-20479 505758
-951532 613082
-890210 663776
767606 -285569
466835 86332...

output:

931.0523112101

result:

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

Test #41:

score: 0
Accepted
time: 1582ms
memory: 9088kb

input:

1
300
370249 -59123
-776101 -977670
-243135 -532403
-579041 96635
569778 -862215
413939 -366298
481224 272525
393367 -40979
483831 994010
-233019 628811
-143918 477955
339126 11331
-107685 517540
622176 -412060
-177324 -205192
431089 749790
-95536 -210836
548410 -707079
616094 -127500
-783278 -72261...

output:

933.7604866928

result:

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

Test #42:

score: 0
Accepted
time: 1612ms
memory: 9148kb

input:

1
300
572725 -213611
493742 -808213
-710052 -380510
893881 -474967
9640 -788263
-459353 580756
-26412 638961
440498 -802856
453695 -912107
22051 -399011
547574 755649
-686907 874963
-504322 -340049
692117 -724428
668948 874184
48863 726276
-663172 -738633
360506 985895
589965 723490
-791113 -581246
...

output:

1077.8413806349

result:

ok found '1077.8413806', expected '1077.8413807', error '0.0000000'

Test #43:

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

input:

1
300
-18347 947891
-18966 947674
-18153 949129
371892 55936
-19040 948495
-19316 948666
-19369 949236
-18720 948324
-19293 949610
-17823 949522
-19243 948220
-18639 948552
-17649 949411
371651 54266
-19228 948586
-17602 948463
-19485 949188
-18243 948112
-17773 948743
372205 54093
-18298 949126
371...

output:

430.9016508304

result:

ok found '430.9016508', expected '430.9016509', error '0.0000000'

Test #44:

score: 0
Accepted
time: 1531ms
memory: 9144kb

input:

1
300
-74242 456694
-526886 299650
-74220 457055
-73487 456305
-73859 456656
61507 -819056
60998 -819121
-526707 299370
-526276 300041
61552 -817655
-526738 299576
-74124 456791
-527186 299008
61978 -818405
-74813 455682
60560 -819145
-73451 455525
-74892 457185
-73693 456477
60721 -818196
60214 -81...

output:

90267.0931341244

result:

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

Test #45:

score: 0
Accepted
time: 1094ms
memory: 8936kb

input:

1
300
574585 394710
574622 393610
-423278 771639
-424926 771360
-424084 771410
-355381 -781788
-355711 -782971
573941 394518
-356559 -782641
-356747 -782401
468958 -215431
-423584 771961
574237 394615
-423230 771874
574235 394702
-424141 771353
-423250 771823
469278 -214864
-423677 771854
470643 -21...

output:

217408.1481352935

result:

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

Test #46:

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

input:

1
300
426446 450150
704880 -177836
705023 -177943
365125 -787336
426646 450111
365336 -787509
-488479 191560
365230 -787626
351178 85715
426393 450079
426499 450252
350929 85788
351095 85697
350955 85774
351185 85404
426289 450343
-488469 191487
365412 -787578
351069 85754
-488205 191341
365332 -787...

output:

20170.8709063751

result:

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

Test #47:

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

input:

1
300
-400243 814451
22608 892635
-400101 814103
6514 778975
993334 -477496
6342 779132
462061 255284
-51701 297766
22472 892564
340929 -448021
479819 -339231
-400286 814390
211825 26983
6556 779317
993060 -477289
993308 -477342
-51535 297899
340706 -447842
340883 -447854
-400416 814256
-400283 8141...

output:

9230.4423163080

result:

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

Test #48:

score: 0
Accepted
time: 802ms
memory: 9024kb

input:

1
300
-474014 -864992
-630838 -307407
-630606 -307503
-124096 -743059
-771964 728691
772586 240106
-772183 728879
391413 526273
199846 912927
428389 -576556
-308290 579377
-255160 -108840
772406 240313
-367068 -161358
772571 240365
-308290 579342
391393 526479
-415239 -4737
-367131 -161451
199868 91...

output:

15025.9748438052

result:

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

Test #49:

score: 0
Accepted
time: 1018ms
memory: 9004kb

input:

1
300
50620 -400031
50739 -399860
510490 905605
-231850 -472272
819819 -32769
556769 430166
510572 905474
-835681 -521539
-892931 517162
308414 643333
726593 422199
864670 -884154
-923273 383788
405709 273425
-479932 -974056
410500 738923
186655 767275
-182443 950085
-567600 -112887
603101 210566
93...

output:

3406.4535451969

result:

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

Test #50:

score: 0
Accepted
time: 1407ms
memory: 9004kb

input:

1
300
176452 -329206
-579449 737212
-127383 552242
979657 -356153
80368 -694513
460265 -812959
445149 141242
-457009 -165865
607661 133016
-790741 -28932
833272 -591475
-579288 737176
-259244 232127
-387178 -302780
176289 -329051
-581332 414202
130425 339972
280492 -57804
-23731 -362222
-538093 -596...

output:

1990.3405678490

result:

ok found '1990.3405678', expected '1990.3405679', error '0.0000000'

Test #51:

score: 0
Accepted
time: 1377ms
memory: 9012kb

input:

1
300
1000000 0
999780 20942
999122 41875
998026 62790
996492 83677
994521 104528
992114 125333
989272 146083
985996 166768
982287 187381
978147 207911
973578 228350
968583 248689
963162 268919
957319 289031
951056 309016
944376 328866
937281 348572
929776 368124
921863 387515
913545 406736
904827 4...

output:

499972.2525363024

result:

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

Test #52:

score: 0
Accepted
time: 1445ms
memory: 8928kb

input:

1
299
1000000 0
999111 42156
996445 84238
992008 126169
985807 167877
977854 209286
968162 250323
956748 290915
943634 330989
928842 370475
912398 409303
894332 447402
874676 484707
853465 521149
830736 556665
806531 591191
780891 624666
753863 657030
725495 688227
695837 718199
664941 746895
632864...

output:

208109.8148594101

result:

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