QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#178261#7241. Black SabbathPhantomThreshold#AC ✓471ms4272kbC++204.1kb2023-09-13 20:20:322023-09-13 20:20:32

Judging History

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

  • [2023-09-13 20:20:32]
  • 评测
  • 测评结果:AC
  • 用时:471ms
  • 内存:4272kb
  • [2023-09-13 20:20:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long double db;
const db eps=1e-8;
int sign(db k){
	if (k>eps) return 1;
	else if (k<-eps) return -1;
	return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}

struct point{
	db x,y;
	point operator + (const point &k1){return (point){x+k1.x,y+k1.y};}
	point operator - (const point &k1){return (point){x-k1.x,y-k1.y};}
	point operator * (db k1){return (point){x*k1,y*k1};}
	point operator / (db k1){return (point){x/k1,y/k1};}
	db abs(){return hypot(x,y);}
	db abs2(){return x*x+y*y;}
	db dis(point k){return ((*this)-k).abs();}
	db dis2(point k){return ((*this)-k).abs2();}
	point unit(){
		db w=abs();
		return (point){x/w,y/w};
	}
	point turn90(){
		return (point){-y,x};	
	}
	int getP() const{
		return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);	
	}
	void print(){
		cerr << "(" << x << "," << y << ") ";	
	}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
int compareangle(point k1,point k2){
	return k1.getP()<k2.getP() || (k1.getP()==k2.getP() && sign(cross(k1,k2))>0);	
}
int checkLL(point k1,point k2,point k3,point k4){
	return cmp(cross(k3-k1,k4-k1),cross(k3-k2,k4-k2))!=0;	
}
point getLL(point k1,point k2,point k3,point k4){
	db w1=cross(k1-k3,k4-k3);
	db w2=cross(k4-k3,k2-k3);
	return (k1*w2+k2*w1)/(w1+w2);
}
struct line{
	point p[2];
	line(point k1,point k2){p[0]=k1;p[1]=k2;}
	point& operator [] (int k){return p[k];}
	int include(point k){return sign(cross(p[1]-p[0],k-p[0]))>0;}
	point dir(){return p[1]-p[0];}
	/*
	line push(){
		const db eps=1e-6;
		point delta=(p[1]-p[0]).turn90().unit()*eps;
		return {p[0]-delta,p[1]-delta};
	}
	*/
	void print(){
		p[0].print();
		p[1].print();	
	}
};
point getLL(line k1,line k2){return getLL(k1[0],k1[1],k2[0],k2[1]);}
int parallel(line k1,line k2){return sign(cross(k1.dir(),k2.dir()))==0;}
int sameDir(line k1,line k2){return parallel(k1,k2) && sign(dot(k1.dir(),k2.dir()))==1;}
int operator < (line k1,line k2){
	if (sameDir(k1,k2)) return k2.include(k1[0]);
	return compareangle(k1.dir(),k2.dir());	
}
int checkpos(line k1,line k2,line k3){return k3.include(getLL(k1,k2));}
vector<line> getHL(vector<line> &L){
	sort(L.begin(),L.end());
	/*
	cerr << "----" << endl;
	for (int i=0;i<(int)L.size();i++){
		L[i].print();
		cerr << endl;	
	}
	*/
	deque<line> q;
	for (int i=0;i<(int)L.size();i++){
		if (i && sameDir(L[i],L[i-1])) continue;
		while (q.size()>1 && !checkpos(q[q.size()-2],q[q.size()-1],L[i])) q.pop_back();
		while (q.size()>1 && !checkpos(q[1],q[0],L[i])) q.pop_front();
		q.push_back(L[i]);
	}
	while (q.size()>2 && !checkpos(q[q.size()-2],q[q.size()-1],q[0])) q.pop_back();
	while (q.size()>2 && !checkpos(q[1],q[0],q[q.size()-1])) q.pop_front();
	vector<line> ans;
	for (int i=0;i<(int)q.size();i++) ans.push_back(q[i]);
	return ans;
}

db w,h;
int n;
point a[1050];
db r[1050];

int main(){
	ios_base::sync_with_stdio(false);
	
	cout << fixed << setprecision(12);
	
	cin >> w >> h >> n;
	
	point C1=(point){0.0,0.0};
	point C2=(point){w,0.0};
	point C3=(point){w,h};
	point C4=(point){0.0,h};
	
	for (int i=1;i<=n;i++){
		cin >> a[i].x >> a[i].y >> r[i];	
	}
	for (int i=1;i<=n;i++){
	//	cerr << "-------------" << endl;
	//	cerr << "i : " << i << endl;
		vector<line> L;
		L.emplace_back(C1,C2);
		L.emplace_back(C2,C3);
		L.emplace_back(C3,C4);
		L.emplace_back(C4,C1);
		for (int j=1;j<=n;j++){
			if (i==j) continue;
			db d2=a[i].dis2(a[j]);
			point P=a[i]+(a[j]-a[i])*((r[i]*r[i]-r[j]*r[j]+d2)/2/d2);
			point Q=P+(a[j]-a[i]).turn90();
			L.emplace_back(P,Q);
		}
		/*
		cerr << "---" << endl;
		for (int i=0;i<(int)L.size();i++){
			L[i].print();
			cerr << endl;	
		}
		*/
		L=getHL(L);
		/*
		cerr << "-----" << endl;
		for (int i=0;i<(int)L.size();i++){
			L[i].print();
			cerr << endl;	
		}
		*/
		int sz=L.size();
		cout << sz << "\n";
		for (int j=0;j<sz;j++){
			point P=getLL(L[j],L[(j+1)%sz]);
			cout << P.x << " " << P.y << "\n";
		}
	}
	return 0;
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

12 10 5
3 2 1
9 2 1
6 5 2
3 8 1
9 8 1

output:

5
6.000000000000 0.000000000000
6.000000000000 1.500000000000
2.500000000000 5.000000000000
-0.000000000000 5.000000000000
-0.000000000000 -0.000000000000
5
12.000000000000 -0.000000000000
12.000000000000 5.000000000000
9.500000000000 5.000000000000
6.000000000000 1.500000000000
6.000000000000 -0.00...

result:

ok Looks like this guy successfully passed all checks with 24 vertices!

Test #2:

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

input:

4 4 1
2 2 1

output:

4
4.000000000000 -0.000000000000
4.000000000000 4.000000000000
-0.000000000000 4.000000000000
-0.000000000000 -0.000000000000

result:

ok Looks like this guy successfully passed all checks with 4 vertices!

Test #3:

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

input:

10000 10000 1
42 1247 1

output:

4
10000.000000000000 -0.000000000000
10000.000000000000 10000.000000000000
-0.000000000000 10000.000000000000
-0.000000000000 -0.000000000000

result:

ok Looks like this guy successfully passed all checks with 4 vertices!

Test #4:

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

input:

10000 10000 1
5000 5000 1

output:

4
10000.000000000000 -0.000000000000
10000.000000000000 10000.000000000000
-0.000000000000 10000.000000000000
-0.000000000000 -0.000000000000

result:

ok Looks like this guy successfully passed all checks with 4 vertices!

Test #5:

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

input:

10000 10000 1
5000 5000 4999

output:

4
10000.000000000000 -0.000000000000
10000.000000000000 10000.000000000000
-0.000000000000 10000.000000000000
-0.000000000000 -0.000000000000

result:

ok Looks like this guy successfully passed all checks with 4 vertices!

Test #6:

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

input:

30 40 10
26 26 3
9 38 1
28 7 1
26 5 1
14 20 10
7 29 1
21 35 4
6 36 2
2 22 1
10 33 2

output:

4
30.000000000000 16.605263157895
30.000000000000 33.722222222222
20.945652173913 28.692028985507
27.139583333333 16.304166666667
4
14.447368421053 36.789473684211
15.250000000000 40.000000000000
6.000000000000 40.000000000000
8.882352941176 35.676470588235
4
30.000000000000 16.605263157895
27.13958...

result:

ok Looks like this guy successfully passed all checks with 49 vertices!

Test #7:

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

input:

100 600 50
72 26 25
93 596 3
69 395 30
57 556 42
92 69 7
70 501 14
12 41 11
6 255 5
54 312 45
57 207 42
55 496 1
44 116 43
90 440 9
97 4 2
11 392 10
15 345 5
22 19 13
69 74 5
92 422 5
21 72 6
3 357 2
56 437 13
36 260 9
65 360 4
27 412 15
12 253 1
20 260 6
60 250 1
12 540 5
9 6 5
86 147 9
12 476 11
9...

output:

7
83.720000000000 0.000000000000
100.000000000000 18.500000000000
100.000000000000 37.392857142857
74.521978021978 56.501373626374
68.657303370787 56.134831460674
41.044642857143 32.466836734694
45.590000000000 -0.000000000000
3
100.000000000000 600.000000000000
72.708333333333 600.000000000000
100....

result:

ok Looks like this guy successfully passed all checks with 258 vertices!

Test #8:

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

input:

89 89 300
7 77 6
38 75 13
33 51 11
71 76 12
7 27 6
41 10 9
72 20 16
23 78 2
56 7 4
15 58 8
38 23 4
50 3 2
87 38 1
67 2 1
7 86 2
18 39 8
52 11 1
29 22 4
27 34 2
41 40 2
65 60 4
27 17 1
83 66 3
21 70 4
65 42 6
4 85 1
54 22 2
32 33 2
52 47 7
19 14 7
84 53 4
84 79 1
46 87 1
80 63 1
15 30 1
34 38 1
9 8 4...

output:

13
9.531250000000 71.437500000000
11.350000000000 72.650000000000
12.562500000000 74.468750000000
13.260869565217 76.913043478261
12.904761904762 79.761904761905
10.066666666667 82.600000000000
8.259259259259 83.277777777778
5.740740740741 83.277777777778
5.285714285714 83.107142857143
-0.0000000000...

result:

ok Looks like this guy successfully passed all checks with 1719 vertices!

Test #9:

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

input:

100 200 300
13 176 12
97 84 2
42 124 41
10 198 1
53 185 14
72 11 10
71 49 27
67 173 4
16 83 7
28 19 18
11 68 8
73 181 5
98 123 1
18 160 2
88 195 4
35 185 3
50 21 3
32 40 3
73 154 2
39 176 2
51 167 2
84 138 3
32 79 4
81 98 5
65 198 1
85 114 3
54 79 5
6 78 3
61 77 2
28 49 6
81 180 2
83 108 2
85 134 1
...

output:

15
16.166666666667 163.833333333333
17.147058823529 164.139705882353
19.750000000000 165.875000000000
23.164948453608 168.948453608247
25.266666666667 173.752380952381
25.266666666667 177.066666666667
23.948717948718 181.679487179487
21.921568627451 184.382352941176
18.600000000000 187.100000000000
...

result:

ok Looks like this guy successfully passed all checks with 1711 vertices!

Test #10:

score: 0
Accepted
time: 38ms
memory: 4084kb

input:

10000 10000 300
3372 203 202
5160 7605 2394
6604 9775 212
8411 2140 1588
5166 3849 1361
1655 5300 1654
45 6988 44
4326 1582 1056
7476 5722 590
8260 7797 711
8217 5098 378
729 7404 644
6435 4973 334
8731 5119 136
475 8172 164
7054 4263 571
2579 9013 545
9116 7201 331
1835 9122 206
6837 1449 130
2725 ...

output:

4
3574.871921182266 0.000000000000
3621.354462839662 362.921382940435
3205.232119853046 438.756763204351
3124.195250659631 0.000000000000
42
5476.370627292531 5211.138105368412
5935.280326473449 5334.374725353058
6148.779352496806 5419.286027951927
6466.229016507789 5587.491257163177
6796.7330480545...

result:

ok Looks like this guy successfully passed all checks with 1713 vertices!

Test #11:

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

input:

10000 10000 10
3681 755 754
807 2144 806
4911 109 108
2372 5565 2371
7485 712 711
4675 2897 1153
9859 1125 140
8086 6332 1913
4149 44 43
8782 1905 1051

output:

5
3913.480769230769 0.000000000000
4497.304728050584 384.289188083928
4968.541073503777 1281.534861315241
2688.331285839273 2339.671429447135
1557.571503131524 -0.000000000000
5
1557.571503131524 0.000000000000
2688.331285839273 2339.671429447135
2627.326888091679 2653.037977239556
-0.000000000000 3...

result:

ok Looks like this guy successfully passed all checks with 49 vertices!

Test #12:

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

input:

10000 4 300
1009 2 1
8490 2 1
189 2 1
9017 2 1
3654 2 1
6329 2 1
2252 2 1
7310 2 1
4347 2 1
4951 2 1
5453 2 1
5197 2 1
8571 2 1
9888 2 1
1982 2 1
5375 2 1
2526 2 1
5034 2 1
6319 2 1
1568 2 1
9446 2 1
7709 2 1
9 2 1
954 2 1
5597 2 1
4101 2 1
1841 2 1
2584 2 1
5732 2 1
1026 2 1
930 2 1
4874 2 1
2097 2...

output:

4
1017.500000000000 0.000000000000
1017.500000000000 4.000000000000
993.500000000000 4.000000000000
993.500000000000 -0.000000000000
4
8530.500000000000 0.000000000000
8530.500000000000 4.000000000000
8471.000000000000 4.000000000000
8471.000000000000 -0.000000000000
4
201.500000000000 0.00000000000...

result:

ok Looks like this guy successfully passed all checks with 1200 vertices!

Test #13:

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

input:

4 10000 300
2 9736 1
2 6117 1
2 6017 1
2 1233 1
2 1127 1
2 2590 1
2 5050 1
2 883 1
2 7659 1
2 8450 1
2 6642 1
2 5156 1
2 4760 1
2 9170 1
2 4165 1
2 6042 1
2 8121 1
2 4648 1
2 3182 1
2 9646 1
2 8348 1
2 4783 1
2 399 1
2 1029 1
2 7713 1
2 8225 1
2 8661 1
2 9100 1
2 5493 1
2 749 1
2 5346 1
2 5601 1
2 2...

output:

4
4.000000000000 9725.500000000000
4.000000000000 9738.000000000000
-0.000000000000 9738.000000000000
0.000000000000 9725.500000000000
4
4.000000000000 6104.000000000000
4.000000000000 6132.500000000000
-0.000000000000 6132.500000000000
0.000000000000 6104.000000000000
4
4.000000000000 6007.50000000...

result:

ok Looks like this guy successfully passed all checks with 1200 vertices!

Test #14:

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

input:

10000 10 300
2969 5 4
8189 7 2
7050 5 4
8873 4 3
9615 4 3
6350 7 2
311 2 1
7813 5 4
7452 8 1
2088 5 4
792 6 3
2767 2 1
8190 3 2
9963 4 3
706 7 2
6204 3 2
7515 4 3
2027 6 3
9363 7 2
2942 7 2
9372 5 4
4609 4 3
8841 8 1
4539 5 4
9241 5 4
5039 6 3
3557 3 2
5170 5 4
3193 8 1
7175 5 4
4024 6 3
6372 4 3
94...

output:

4
2980.785714285714 0.000000000000
2979.357142857143 10.000000000000
2955.574074074074 10.000000000000
2954.833333333333 -0.000000000000
4
8194.500000000000 6.250000000000
8196.000000000000 10.000000000000
8181.928571428571 10.000000000000
8182.412280701754 3.228070175439
5
7063.125000000000 0.00000...

result:

ok Looks like this guy successfully passed all checks with 1215 vertices!

Test #15:

score: 0
Accepted
time: 36ms
memory: 4004kb

input:

10 10000 300
8 3727 1
7 1518 2
3 9599 2
5 7680 4
7 3988 2
7 775 2
5 1645 4
5 5719 4
3 9667 2
7 7730 2
6 344 3
2 3058 1
2 7104 1
2 210 1
2 6995 1
4 5862 3
8 8453 1
6 3193 3
5 456 4
4 815 3
3 8466 2
7 636 2
4 140 3
5 4856 4
7 5655 2
7 3326 2
4 8313 3
6 9360 3
6 7186 3
6 728 3
6 5555 3
2 5813 1
2 6277 ...

output:

4
10.000000000000 3770.000000000000
-0.000000000000 3770.000000000000
0.000000000000 3706.714285714286
10.000000000000 3705.285714285714
4
10.000000000000 1524.500000000000
7.800000000000 1524.500000000000
1.235294117647 1516.294117647059
10.000000000000 1514.833333333333
4
10.000000000000 9583.5937...

result:

ok Looks like this guy successfully passed all checks with 1218 vertices!

Test #16:

score: 0
Accepted
time: 468ms
memory: 4112kb

input:

201 201 1000
107 62 61
18 43 17
27 97 26
78 177 23
131 2 1
11 13 10
147 189 11
3 5 1
56 114 7
44 42 4
189 159 11
118 129 6
40 183 15
31 8 7
20 70 1
60 103 1
123 142 7
190 18 10
39 30 7
28 68 2
15 123 2
190 31 2
176 107 21
76 8 1
18 178 7
198 32 2
107 194 6
134 163 16
195 91 3
171 145 11
167 180 10
1...

output:

90
112.666666666667 0.000000000000
126.500000000000 4.150000000000
128.989361702128 5.021276595745
133.595890410959 7.006849315068
137.677777777778 9.233333333333
141.475510204082 11.597959183673
143.854609929078 13.290780141844
147.188524590164 16.024590163934
150.831460674157 19.505617977528
151.3...

result:

ok Looks like this guy successfully passed all checks with 5802 vertices!

Test #17:

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

input:

100 400 1000
37 176 36
41 29 28
64 210 7
64 94 35
81 36 12
95 54 4
11 145 4
61 2 1
27 95 1
32 229 17
60 145 2
10 301 9
43 280 30
10 75 9
73 211 1
16 13 1
27 322 14
79 207 6
27 357 20
90 156 9
88 183 11
8 110 7
27 91 2
79 311 17
4 11 3
12 53 9
12 233 3
77 198 3
67 220 3
17 119 5
92 229 7
93 133 6
67 ...

output:

50
38.194915254237 139.915254237288
42.897435897436 140.410256410256
47.000000000000 141.297297297297
49.166666666667 142.000000000000
51.850000000000 143.150000000000
56.273706896552 145.428879310345
59.625954198473 147.916030534351
64.094339622642 151.905660377358
67.415094339623 156.584905660377
...

result:

ok Looks like this guy successfully passed all checks with 5777 vertices!

Test #18:

score: 0
Accepted
time: 466ms
memory: 4272kb

input:

400 100 1000
74 24 23
53 84 15
3 40 2
121 37 25
278 90 9
243 5 4
392 52 7
66 57 10
196 11 10
361 30 29
137 73 14
29 35 23
228 85 14
11 12 6
269 29 28
126 86 2
159 92 7
348 82 17
216 20 11
329 57 12
212 41 10
160 53 16
392 38 2
377 69 13
61 3 1
232 48 11
9 80 8
95 49 3
179 15 7
121 91 4
247 82 5
224 ...

output:

31
78.166666666667 0.000000000000
87.500000000000 5.090909090909
88.833333333333 6.000000000000
89.020000000000 6.160000000000
91.287234042553 8.553191489362
94.020833333333 12.458333333333
94.776315789474 13.736842105263
96.878048780488 19.341463414634
97.955631399317 25.160409556314
95.77889447236...

result:

ok Looks like this guy successfully passed all checks with 5773 vertices!

Test #19:

score: 0
Accepted
time: 466ms
memory: 4148kb

input:

10000 10000 1000
9530 4648 469
9605 567 394
994 472 471
1186 3623 1185
8729 9835 164
4697 1162 1161
9333 6189 666
5870 8544 1455
5226 6209 967
9870 1377 129
1588 8748 1251
3244 6363 1020
5917 3942 1402
9616 992 31
1357 6380 866
8663 3702 814
491 2195 403
8880 763 356
7186 6853 687
3744 220 178
3168 ...

output:

20
9731.758013579662 4221.449076267172
9866.958919687278 4304.144776119403
10000.000000000000 4456.142487046632
10000.000000000000 4896.064257028112
9948.200782875287 4944.535010401839
9746.270071116442 5104.330573644075
9717.381150325752 5118.682441344578
9510.365289493668 5126.667338833816
9309.48...

result:

ok Looks like this guy successfully passed all checks with 5834 vertices!

Test #20:

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

input:

500 500 1000
444 342 55
78 30 29
211 352 147
322 20 19
25 163 24
308 62 25
351 11 10
94 164 44
440 284 3
407 148 92
185 105 64
3 352 2
20 419 19
231 157 5
59 329 6
64 479 20
482 393 8
6 32 5
173 4 3
146 6 5
443 456 43
64 377 2
106 13 3
8 382 7
205 9 8
288 209 15
195 28 13
93 75 18
96 491 8
77 106 16...

output:

36
446.000000000000 287.000000000000
450.796296296296 287.342592592593
456.937306501548 288.189628482972
465.052631578947 290.894736842105
472.281690140845 294.577464788732
477.839694656489 298.320610687023
482.995588235294 302.691911764706
490.718791946309 312.244295302013
500.000000000000 330.4629...

result:

ok Looks like this guy successfully passed all checks with 5818 vertices!

Test #21:

score: 0
Accepted
time: 264ms
memory: 4104kb

input:

4 10000 1000
2 942 1
2 9551 1
2 8977 1
2 7840 1
2 4973 1
2 5125 1
2 4960 1
2 8782 1
2 5045 1
2 5415 1
2 5978 1
2 5709 1
2 6218 1
2 6009 1
2 1071 1
2 6926 1
2 1312 1
2 533 1
2 6814 1
2 8143 1
2 2051 1
2 1223 1
2 4184 1
2 2134 1
2 5491 1
2 2948 1
2 4883 1
2 1493 1
2 7886 1
2 9447 1
2 9660 1
2 6081 1
2...

output:

4
4.000000000000 940.500000000000
4.000000000000 945.500000000000
-0.000000000000 945.500000000000
0.000000000000 940.500000000000
4
4.000000000000 9541.500000000000
4.000000000000 9554.000000000000
-0.000000000000 9554.000000000000
0.000000000000 9541.500000000000
4
4.000000000000 8975.500000000000...

result:

ok Looks like this guy successfully passed all checks with 4000 vertices!

Test #22:

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

input:

10000 4 1000
5567 2 1
4650 2 1
2143 2 1
6000 2 1
8233 2 1
6646 2 1
1322 2 1
6946 2 1
8011 2 1
6906 2 1
3987 2 1
8019 2 1
6334 2 1
2249 2 1
7615 2 1
3145 2 1
4665 2 1
2968 2 1
5082 2 1
3331 2 1
1958 2 1
7707 2 1
6470 2 1
3234 2 1
9701 2 1
8128 2 1
2157 2 1
1357 2 1
8919 2 1
1650 2 1
8211 2 1
9851 2 1...

output:

4
5574.000000000000 0.000000000000
5574.000000000000 4.000000000000
5565.500000000000 4.000000000000
5565.500000000000 -0.000000000000
4
4653.000000000000 0.000000000000
4653.000000000000 4.000000000000
4648.000000000000 4.000000000000
4648.000000000000 -0.000000000000
4
2145.000000000000 0.00000000...

result:

ok Looks like this guy successfully passed all checks with 4000 vertices!

Test #23:

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

input:

100 10000 1000
82 4989 17
43 2258 42
61 4777 38
15 5751 14
59 2817 40
80 8409 19
26 9575 25
15 9248 14
61 1140 38
16 137 15
8 3416 7
90 5299 9
16 1836 15
25 8726 24
5 7096 4
73 1072 26
89 525 10
46 421 45
73 6088 26
3 6174 2
58 6469 41
19 913 18
64 3761 35
83 4412 16
30 8311 29
75 1969 24
49 8498 48...

output:

6
100.000000000000 4978.681818181818
100.000000000000 5014.080645161290
69.496960486322 5005.224924012158
62.177539608574 4991.149114631873
72.663418708241 4965.762249443207
78.654761904762 4964.128246753247
9
63.055555555556 2219.111111111111
78.655172413793 2233.793103448276
84.270573566085 2246.0...

result:

ok Looks like this guy successfully passed all checks with 5359 vertices!

Test #24:

score: 0
Accepted
time: 471ms
memory: 4272kb

input:

10000 100 1000
2935 67 32
4181 39 38
2357 5 4
3582 62 37
2589 39 38
7681 19 18
4487 46 45
8336 53 46
3665 27 26
8547 7 6
8228 44 43
3958 2 1
3872 84 15
7022 41 40
9888 96 3
4095 65 34
5833 63 36
9505 97 2
7352 70 29
928 66 33
1086 12 11
876 37 26
1337 78 21
488 24 23
1729 47 46
8387 10 9
4853 96 3
3...

output:

8
2949.123786407767 31.279530744337
2966.015789473684 55.209868421053
2969.238568588469 72.532306163022
2952.189655172414 100.000000000000
2918.882352941176 100.000000000000
2902.638949671772 81.590809628009
2896.641223053234 65.175978882534
2925.757445400397 20.461780277962
9
4205.977777777778 0.00...

result:

ok Looks like this guy successfully passed all checks with 5353 vertices!

Test #25:

score: 0
Accepted
time: 460ms
memory: 4104kb

input:

10000 10000 1000
7940 3750 60
3320 1300 60
1300 3950 60
7760 5400 60
3080 700 60
5020 6250 60
880 2200 60
760 3300 60
6500 5750 60
6300 9450 60
2660 4550 60
4260 8550 60
1260 8050 60
3100 9850 60
4420 3350 60
9820 4250 60
3120 5000 60
6660 8950 60
2940 6650 60
2500 6950 60
7000 7700 60
7880 9900 60
...

output:

6
8095.535714285714 3741.785714285714
8054.107142857143 3990.357142857143
7999.419642857143 4073.482142857143
7784.464285714286 3758.214285714286
7795.535714285714 3691.785714285714
8004.464285714286 3608.214285714286
6
3475.535714285714 1291.785714285714
3464.464285714286 1358.214285714286
3255.535...

result:

ok Looks like this guy successfully passed all checks with 5890 vertices!

Test #26:

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

input:

100 100 1000
24 9 1
30 12 1
57 42 1
84 93 1
84 30 1
69 27 1
30 30 1
48 69 1
18 27 1
27 30 1
75 3 1
18 33 1
81 72 1
33 87 1
84 6 1
6 33 1
33 93 1
42 51 1
42 81 1
30 45 1
33 57 1
12 87 1
27 15 1
45 51 1
48 84 1
69 36 1
42 60 1
21 57 1
9 75 1
39 48 1
84 39 1
54 21 1
63 6 1
93 45 1
51 63 1
66 81 1
33 84...

output:

4
25.500000000000 7.500000000000
25.500000000000 10.500000000000
22.500000000000 10.500000000000
22.500000000000 7.500000000000
4
31.500000000000 10.500000000000
31.500000000000 13.500000000000
28.500000000000 13.500000000000
28.500000000000 10.500000000000
4
58.500000000000 40.500000000000
58.50000...

result:

ok Looks like this guy successfully passed all checks with 4090 vertices!

Test #27:

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

input:

130 130 1000
53 31 1
73 51 1
123 51 1
19 53 1
113 21 1
98 46 1
64 78 1
89 53 1
122 34 1
26 12 1
6 42 1
34 58 1
117 19 1
13 111 1
54 118 1
43 111 1
66 12 1
74 128 1
90 110 1
51 117 1
111 97 1
4 28 1
107 19 1
86 22 1
74 8 1
122 14 1
89 83 1
84 48 1
36 92 1
85 15 1
52 74 1
61 47 1
44 68 1
83 31 1
14 68...

output:

5
55.500000000000 28.500000000000
53.500000000000 34.500000000000
52.333333333333 34.666666666667
51.000000000000 32.000000000000
53.000000000000 26.000000000000
6
74.000000000000 48.000000000000
76.000000000000 52.000000000000
74.000000000000 53.000000000000
69.500000000000 51.500000000000
70.50000...

result:

ok Looks like this guy successfully passed all checks with 5006 vertices!

Test #28:

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

input:

103 103 1000
77 49 1
48 46 1
39 63 1
53 51 1
67 79 1
34 78 1
54 18 1
35 45 1
33 11 1
68 26 1
53 11 1
48 56 1
8 46 1
81 27 1
13 61 1
32 14 1
99 33 1
6 32 1
73 81 1
94 78 1
13 41 1
29 93 1
7 59 1
49 33 1
37 9 1
77 19 1
27 59 1
49 53 1
23 21 1
4 38 1
59 43 1
55 65 1
21 97 1
35 85 1
9 73 1
101 67 1
65 8...

output:

4
79.000000000000 48.000000000000
78.000000000000 51.000000000000
75.000000000000 50.000000000000
76.000000000000 47.000000000000
4
50.000000000000 45.000000000000
49.000000000000 48.000000000000
46.000000000000 47.000000000000
47.000000000000 44.000000000000
4
41.000000000000 62.000000000000
40.000...

result:

ok Looks like this guy successfully passed all checks with 4040 vertices!

Test #29:

score: 0
Accepted
time: 450ms
memory: 3980kb

input:

8000 10000 1000
3450 30 29
7110 4080 100
3960 7080 100
4740 4830 100
710 6960 100
2040 9210 100
4200 4440 100
6200 3540 100
5990 5850 100
2600 5160 100
5890 2730 100
4980 2190 100
6330 6330 100
470 3270 100
5240 1440 100
5080 5310 100
7980 840 19
480 7380 100
6550 8130 100
950 4320 100
3040 2430 100...

output:

4
3665.190540540541 0.000000000000
3643.180805687204 54.290679304897
3431.159952606635 204.472116903633
3339.147500000000 -0.000000000000
8
7266.137440758294 3892.527646129542
7337.298578199052 4050.663507109005
7309.691943127962 4118.759873617694
7127.322274881517 4247.938388625592
6876.56398104265...

result:

ok Looks like this guy successfully passed all checks with 5891 vertices!

Extra Test:

score: 0
Extra Test Passed