QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#24112 | #2950. Growing Some Oobleck | maze# | TL | 6ms | 3868kb | C++14 | 2.8kb | 2022-03-26 15:13:18 | 2022-04-30 04:57:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 110
#define eps 1e-8
struct circle
{
double x, y;
double r;
double s;
int id;
};
vector<circle> S;
double dist(circle &c1, circle &c2)
{
return sqrt((c1.x - c2.x) * (c1.x - c2.x) + (c1.y - c2.y) * (c1.y - c2.y)) - sqrt((c1.r + c2.r) * (c1.r + c2.r));
}
bool intersect(circle &c1, circle &c2)
{
return dist(c1, c2) < eps;
}
double getT()
{
double t = 1e18;
for (circle &c1 : S)
{
for (circle &c2 : S)
{
if (c1.id == c2.id)
continue;
t = min(t, dist(c1, c2) / (c1.s + c2.s));
}
}
return t;
}
void addT(double t)
{
for (circle &c : S)
c.r += c.s * t;
}
int f[N];
int getf(int k)
{
if (f[k] == k)
return k;
return f[k] = getf(f[k]);
}
void qmerge(int a, int b)
{
int t1 = getf(a);
int t2 = getf(b);
if (t1 != t2)
f[t1] = t2;
}
circle temp[N];
int cntf[N];
void merge()
{
int sz = S.size();
for (int i = 0; i < N; i++)
f[i] = i;
for (circle &c1 : S)
{
for (circle &c2 : S)
{
if (c1.id == c2.id)
continue;
if (intersect(c1, c2))
{
qmerge(c1.id, c2.id);
}
}
}
// todo
for (int i = 1; i <= sz; i++)
{
temp[i].id = i;
temp[i].r = 0;
temp[i].x = 0;
temp[i].y = 0;
temp[i].s = 0;
cntf[i] = 0;
}
for (circle &c : S)
{
int fa = getf(c.id);
temp[fa].x += c.x;
temp[fa].y += c.y;
temp[fa].r += c.r * c.r;
temp[fa].s = max(temp[fa].s, c.s);
cntf[fa]++;
}
S.clear();
int cnt = 0;
for (int i = 1; i <= sz; i++)
{
if (getf(i) == i)
{
circle c;
c.id = ++cnt;
c.r = sqrt(temp[i].r);
c.x = temp[i].x / cntf[i];
c.y = temp[i].y / cntf[i];
c.s = temp[i].s;
S.push_back(c);
}
}
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
circle c;
c.id = i;
scanf("%lf%lf%lf%lf", &c.x, &c.y, &c.r, &c.s);
S.push_back(c);
}
while (S.size() > 1)
{
double t = getT();
// for (circle &c : S)
// {
// printf("%.8f %.8f %.8f\n", c.x, c.y, c.r);
// }
while (t < eps)
{
merge();
t = getT();
}
if (S.size() > 1)
addT(t);
}
for (circle &c : S)
{
printf("%.8f %.8f\n%.8f\n", c.x, c.y, c.r);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3780kb
input:
3 10 10 5 1 24 10 7 1 16 2 2 1
output:
16.50000000 6.00000000 10.44030651
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
5 -5 0 1 1 6 0 1 1 0 7 1 1 0 -8 1 1 0 0 1 2
output:
1.18750000 -3.12500000 7.61677681
result:
ok 3 numbers
Test #3:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
2 -1000000000 0 1 1 1000000000 0 1 1
output:
0.00000000 0.00000000 1414213562.37309504
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 3ms
memory: 3720kb
input:
4 -100000000 -1000000000 1 2 1000000000 -1000000000 1 2 -1000000000 1000000000 1 3 1000000000 1000000000 1 3
output:
225000000.00000000 0.00000000 1673350486.96081042
result:
ok 3 numbers
Test #5:
score: 0
Accepted
time: 3ms
memory: 3652kb
input:
4 -100000000 -1000000000 1 1000000 1000000000 -1000000000 1 1000000 -1000000000 1000000000 1 3 1000000000 1000000000 1 3
output:
-137500000.00000000 500000000.00000000 2074241311.01239991
result:
ok 3 numbers
Test #6:
score: 0
Accepted
time: 4ms
memory: 3652kb
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.58984375 1.00000000 13239.14279214
result:
ok 3 numbers
Test #7:
score: 0
Accepted
time: 3ms
memory: 3796kb
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.00000000 -10640.58984375 13239.14279214
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 3ms
memory: 3796kb
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.00000000 0.00000000 725.25869849
result:
ok 3 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
4 0 1 2 3 7 1 3 1 17 1 1 1 17 10 1 1
output:
13.62500000 5.50000000 11.22914734
result:
ok 3 numbers
Test #10:
score: 0
Accepted
time: 3ms
memory: 3816kb
input:
4 0 1 2 1 7 1 3 3 17 1 1 1 17 10 1 1
output:
13.62500000 5.50000000 11.24583256
result:
ok 3 numbers
Test #11:
score: 0
Accepted
time: 6ms
memory: 3800kb
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.00000000 10.00000000 25.64861087
result:
ok 3 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3800kb
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.00000000 261.24908550 375.56894691
result:
ok 3 numbers
Test #13:
score: 0
Accepted
time: 3ms
memory: 3776kb
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.15356445 107695.57861328 84684.98156049
result:
ok 3 numbers
Test #14:
score: 0
Accepted
time: 3ms
memory: 3756kb
input:
3 -1000000000 0 1 100000 1000000000 0 1 100000 1000000000 1000000000 1000000 1
output:
0.00000000 250000000.00000000 1457737973.71136975
result:
ok 3 numbers
Test #15:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
4 -1000000000 0 1 100000 1000000000 0 1 100000 1000000000 1000000000 1000000 1 0 0 2 2
output:
250000000.00000000 250000000.00000000 1414185636.99780464
result:
ok 3 numbers
Test #16:
score: -100
Time Limit Exceeded
input:
100 -993853835 -889234028 372418 480830 967974474 863745382 845086 316834 902310614 -902493899 405732 380202 -37824102 -287741231 400050 942967 971969049 92047940 468507 921761 -600612683 -278056632 977642 172884 235442253 851973492 855665 943236 407860875 592755649 345538 823894 227087840 -93883735...