QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#28341 | #2950. Growing Some Oobleck | hld67890# | TL | 2ms | 2008kb | C++17 | 2.4kb | 2022-04-13 17:45:34 | 2022-04-29 09:39:06 |
Judging History
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