QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#24112#2950. Growing Some Oobleckmaze#TL 6ms3868kbC++142.8kb2022-03-26 15:13:182022-04-30 04:57:29

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-30 04:57:29]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:3868kb
  • [2022-03-26 15:13:18]
  • 提交

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;
}

詳細信息

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...

output:


result: