QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#28341#2950. Growing Some Oobleckhld67890#TL 2ms2008kbC++172.4kb2022-04-13 17:45:342022-04-29 09:39:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 09:39:06]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:2008kb
  • [2022-04-13 17:45:34]
  • 提交

answer

#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

const double eps = 1e-11;
struct node {
	double x , y , r , s;
	int del;
} a[120] , b[120];
int n;
double dis ( double x1 , double y1 , double x2 , double y2 ) {
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double gettime () {
	int i , j;
	double ret = 1e15;
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = i + 1 ; j <= n ; j++ ) {
			//printf ( "%lf %lf\n" , dis (a[i].x,a[i].y,a[j].x,a[j].y)-a[i].r-a[j].r , a[i].s+a[j].s );
			ret = min ( ret , (dis (a[i].x,a[i].y,a[j].x,a[j].y)-a[i].r-a[j].r) / (a[i].s+a[j].s) );
		}
	}
	return ret;
}
void expand ( double t ) {
	int i;
	for ( i = 1 ; i <= n ; i++ ) {
		a[i].r += t * a[i].s;
	}
}
int touch ( node x1 , node x2 ) {
	if ( dis(x1.x,x1.y,x2.x,x2.y) - x1.r - x2.r < eps ) return 1;
	return 0;
}
void merge () {
	int i , j , cnt , m;
	int fi = -1 , fj;
	node now , nnow;
	for ( i = 1 ; i <= n ; i++ ) {
		for ( j = i + 1 ; j <= n ; j++ ) {
			if ( touch ( a[i] , a[j] ) == 1 ) {
				fi = i;
				fj = j;
				break;
			}
		}
		if ( fi != -1 ) break;
	}
	now.x = (a[fi].x + a[fj].x) / 2;
	now.y = (a[fi].y + a[fj].y) / 2;
	now.r = sqrt ( a[fi].r*a[fi].r + a[fj].r * a[fj].r );
	now.s = max ( a[fi].s , a[fj].s );
	now.del = 0;
	//printf ( "@@%lf\n" , now.r );
	a[i].del = 1;
	a[j].del = 1;
	for ( i = 2 ; i <= n ; i++ ) {
		nnow = now;
		nnow.r = nnow.r * nnow.r;
		cnt = 1;
		for ( j = 1 ; j <= n ; j++ ) {
			if ( a[j].del == 0 ) {
				if ( touch ( now , a[j] ) == 1 ) {
					nnow.x += a[j].x;
					nnow.y += a[j].y;
					nnow.r += a[j].r * a[j].r;
					nnow.s = max ( nnow.s , a[j].s );
					cnt++;
					a[j].del = 1;
				}
			}
		}
		if ( cnt == 1 ) break;
		nnow.r = sqrt ( nnow.r );
		nnow.x /= cnt;
		nnow.y /= cnt;
		now = nnow;
	}
	m = 1;
	b[1] = now;
	for ( i = 1 ; i <= n ; i++ ) {
		if ( a[i].del == 0 ) b[++m] = a[i];
	}
	for ( i = 1 ; i <= m ; i++ ) {
		a[i] = b[i];
	}
	n = m;
}
void work () {
	int i;
	double t;
	scanf ( "%d" , &n );
	for ( i = 1 ; i <= n ; i++ ) {
		//a[i].x = i*i; a[i].y = 0; a[i].r = 0.1; a[i].s = 0;
		scanf ( "%lf%lf%lf%lf" , &a[i].x , &a[i].y , &a[i].r , &a[i].s );
	}
	while ( n > 1 ) {
		t = gettime ();
		expand ( t );
		merge ();
		//printf ( "%d\n" , n );
	}
	printf ( "%.10lf %.10lf\n" , a[1].x , a[1].y );
	printf ( "%.10lf\n" , a[1].r );
}
int main () {
	work ();
	return 0;
}

详细

Test #1:

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

input:

3
10 10 5 1
24 10 7 1
16 2 2 1

output:

16.5000000000 6.0000000000
10.4403065089

result:

ok 3 numbers

Test #2:

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

input:

5
-5 0 1 1
6 0 1 1
0 7 1 1
0 -8 1 1
0 0 1 2

output:

1.1875000000 -3.1250000000
7.6167768131

result:

ok 3 numbers

Test #3:

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

input:

2
-1000000000 0 1 1
1000000000 0 1 1

output:

0.0000000000 0.0000000000
1414213562.3730950356

result:

ok 3 numbers

Test #4:

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

input:

4
-100000000 -1000000000 1 2
1000000000 -1000000000 1 2
-1000000000 1000000000 1 3
1000000000 1000000000 1 3

output:

225000000.0000000000 0.0000000000
1673350486.9608104229

result:

ok 3 numbers

Test #5:

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

input:

4
-100000000 -1000000000 1 1000000
1000000000 -1000000000 1 1000000
-1000000000 1000000000 1 3
1000000000 1000000000 1 3

output:

-137500000.0000000000 500000000.0000000000
2074241311.0123999119

result:

ok 3 numbers

Test #6:

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

input:

10
-1 1 1 1
3 1 1 1
8 1 1 1
21 1 1 1
55 1 1 1
155 1 1 1
355 1 1 1
900 1 1 1
2000 1 1 1
20000 1 1 1

output:

10640.5898437500 1.0000000000
13239.1427921418

result:

ok 3 numbers

Test #7:

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

input:

10
1 1 1 1
1 -3 1 1
1 -8 1 1
1 -21 1 1
1 -55 1 1
1 -155 1 1
1 -355 1 1
1 -900 1 1
1 -2000 1 1
1 -20000 1 1

output:

1.0000000000 -10640.5898437500
13239.1427921418

result:

ok 3 numbers

Test #8:

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

input:

8
-1 1 1 2
-5 5 1 2
0 6 1 1
-6 0 1 1
1001 -1 1 3
1005 -5 1 3
1006 0 1 1
1000 -6 1 1

output:

500.0000000000 0.0000000000
725.2586984934

result:

ok 3 numbers

Test #9:

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

input:

4
0 1 2 3
7 1 3 1
17 1 1 1
17 10 1 1

output:

13.6250000000 5.5000000000
11.2291473407

result:

ok 3 numbers

Test #10:

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

input:

4
0 1 2 1
7 1 3 3
17 1 1 1
17 10 1 1

output:

13.6250000000 5.5000000000
11.2458325614

result:

ok 3 numbers

Test #11:

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

input:

100
0 0 1 1
0 10 1 1
0 20 1 1
0 30 1 1
0 40 1 1
0 50 1 1
0 60 1 1
0 70 1 1
0 80 1 1
0 90 1 1
0 100 1 1
0 110 1 1
0 120 1 1
0 130 1 1
0 140 1 1
0 150 1 1
0 160 1 1
0 170 1 1
0 180 1 1
0 190 1 1
0 200 1 1
0 210 1 1
0 220 1 1
0 230 1 1
0 240 1 1
0 250 1 1
0 260 1 1
0 270 1 1
0 280 1 1
0 290 1 1
0 300 1...

output:

0.0000000000 10.0000000000
25.6486108721

result:

ok 3 numbers

Test #12:

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

input:

100
0 0 1 1
0 10 1 1
0 20 1 1
0 30 1 1
0 40 1 1
0 50 1 1
0 60 1 1
0 70 1 1
0 80 1 1
0 90 1 1
0 100 1 1
0 110 1 1
0 120 1 1
0 130 1 1
0 140 1 1
0 150 1 1
0 160 1 1
0 170 1 1
0 180 1 1
0 190 1 1
0 200 1 1
0 210 1 1
0 220 1 1
0 230 1 1
0 240 1 1
0 250 1 1
0 260 1 1
0 270 1 1
0 280 1 1
0 290 1 1
0 300 1...

output:

50.0000000000 261.2490855048
375.5689469117

result:

ok 3 numbers

Test #13:

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

input:

100
0 0 1 1
10 20 1 1
20 80 1 1
30 180 1 1
40 320 1 1
50 500 1 1
60 720 1 1
70 980 1 1
80 1280 1 1
90 1620 1 1
100 2000 1 1
110 2420 1 1
120 2880 1 1
130 3380 1 1
140 3920 1 1
150 4500 1 1
160 5120 1 1
170 5780 1 1
180 6480 1 1
190 7220 1 1
200 8000 1 1
210 8820 1 1
220 9680 1 1
230 10580 1 1
240 11...

output:

681.1535644531 107695.5786132812
84684.9815604907

result:

ok 3 numbers

Test #14:

score: -100
Time Limit Exceeded

input:

3
-1000000000 0 1 100000
1000000000 0 1 100000
1000000000 1000000000 1000000 1

output:


result: