QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#660539#2950. Growing Some Oobleckenze114514AC ✓2ms3960kbC++203.3kb2024-10-20 11:56:382024-10-20 11:56:39

Judging History

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

  • [2024-10-20 11:56:39]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3960kb
  • [2024-10-20 11:56:38]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

#define pb push_back

const ld pi = 3.14159265358979323846;
const ll INF = 1e18;
const ld eps = 1e-9;

template<typename T>
T chmax(T a, T b) {
    return a > b ? a : b;
}

template<typename T>
T chmin(T a, T b) {
    return a > b ? b : a;
}

struct Circle {
    ld x, y, r, s;
    bool del;
};

int n;
Circle a[120], b[120];

ld dis(ld x1, ld y1, ld x2, ld y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

ld gettime() {
    ld ret = INF;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (a[i].del || a[j].del) continue;
            ld dist = dis(a[i].x, a[i].y, a[j].x, a[j].y);
            ld sum_r = a[i].r + a[j].r;
            ld delta_r = a[i].s + a[j].s;
            if (delta_r == 0) continue;
            ret = chmin(ret, (dist - sum_r) / delta_r);
        }
    }
    return ret;
}

void expand(ld t) {
    for (int i = 1; i <= n; i++) {
        if (!a[i].del) {
            a[i].r += t * a[i].s;
        }
    }
}

bool touch(Circle x1, Circle x2) {
    return dis(x1.x, x1.y, x2.x, x2.y) <= x1.r + x2.r + eps;
}

void merge() {
    int fi = -1, fj = -1;
    for (int i = 1; i <= n; i++) {
        if (a[i].del) continue;
        for (int j = i + 1; j <= n; j++) {
            if (a[j].del) continue;
            if (touch(a[i], a[j])) {
                fi = i;
                fj = j;
                break;
            }
        }
        if (fi != -1) break;
    }

    Circle now;
    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 = chmax(a[fi].s, a[fj].s);
    now.del = false;

    a[fi].del = true;
    a[fj].del = true;

    bool anyNewMerges = true;
    while (anyNewMerges) {
        anyNewMerges = false;
        int cnt = 1;
        ld total_area = now.r * now.r * pi;
        ld sumX = now.x, sumY = now.y;

        for (int i = 1; i <= n; i++) {
            if (!a[i].del && touch(now, a[i])) {
                sumX += a[i].x;
                sumY += a[i].y;
                total_area += a[i].r * a[i].r * pi;
                now.s = chmax(now.s, a[i].s);
                a[i].del = true;
                cnt++;
                anyNewMerges = true;
            }
        }
        if (cnt > 1) {
            now.x = sumX / cnt;
            now.y = sumY / cnt;
            now.r = sqrt(total_area / pi);
        }
    }

    int m = 0;
    b[m++] = now;
    for (int i = 1; i <= n; i++) {
        if (!a[i].del) b[m++] = a[i];
    }
    for (int i = 0; i < m; i++) {
        a[i + 1] = b[i];
    }
    n = m;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].r >> a[i].s;
        a[i].del = false;
    }

    while (n > 1) {
        ld t = gettime();
        expand(t);
        merge();
    }

    cout << fixed << setprecision(10) << a[1].x << " " << a[1].y << endl;
    cout << fixed << setprecision(10) << a[1].r << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    while (t--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3788kb

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: 0ms
memory: 3944kb

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: 0ms
memory: 3816kb

input:

2
-1000000000 0 1 1
1000000000 0 1 1

output:

0.0000000000 0.0000000000
1414213562.3730950488

result:

ok 3 numbers

Test #4:

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

input:

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

output:

225000000.0000000000 0.0000000000
1673350486.9608103293

result:

ok 3 numbers

Test #5:

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

input:

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

output:

-137500000.0000000000 500000000.0000000000
2074241311.0123999461

result:

ok 3 numbers

Test #6:

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

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: 0ms
memory: 3824kb

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: 0ms
memory: 3888kb

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: 3812kb

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: 0ms
memory: 3696kb

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: 3888kb

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: 3900kb

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: 0ms
memory: 3900kb

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: 0
Accepted
time: 0ms
memory: 3884kb

input:

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

output:

0.0000000000 250000000.0000000000
1457737973.7113698217

result:

ok 3 numbers

Test #15:

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

input:

4
-1000000000 0 1 100000
1000000000 0 1 100000
1000000000 1000000000 1000000 1
0 0 2 2

output:

250000000.0000000000 250000000.0000000000
1414185636.9978044289

result:

ok 3 numbers

Test #16:

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

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:

712148141.4580076847 752427048.4484272641
940126064.8112806365

result:

ok 3 numbers

Test #17:

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

input:

100
-991006979 -78398598 888529 6397
-168191015 86162807 953291 446246
-941099384 195245041 482901 602525
843205725 396143650 458929 285642
-170766083 -799927656 886603 482177
-398289374 544239452 298537 456698
-873551763 873954869 686379 697063
-874344706 -15896687 396572 296644
151301482 -63675804...

output:

371827339.3973156293 266951144.2422654964
1209296596.1145499555

result:

ok 3 numbers

Test #18:

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

input:

100
-174958760 -871174978 565937 356774
-925634674 -432225577 701564 37257
-22555735 211243118 48552 255475
714731061 136239021 326781 837955
-932589505 37077711 508137 17719
-979235051 376608958 350534 645908
288796461 -543046646 582992 37683
172529142 294162972 97262 459348
-615050639 378778468 44...

output:

198360260.4611066315 170910810.3947414226
1440508744.0124546422

result:

ok 3 numbers

Test #19:

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

input:

100
641089458 483532290 243344 707151
464405314 -950613961 449837 114062
895987914 227241195 99998 394220
586256397 -123665608 708837 390270
453070722 874083079 615466 553261
587302921 208978464 888327 320914
-548855314 187435488 479604 864098
-780597010 604222630 797951 107848
766080888 -753168664 ...

output:

-131644699.4493794335 639893986.2908795675
1135881519.5623235786

result:

ok 3 numbers

Test #20:

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

input:

100
-690345971 -309244090 434956 543324
-293038345 678481303 198110 705072
-332952084 243239272 665648 47171
457781733 -383570237 576688 942583
-308752700 -436395201 237000 88803
6357244 41347970 940324 510123
760976558 917917621 862012 204718
413760485 914282289 498641 756346
-271233 262367852 4759...

output:

231242612.1222124735 -300376760.2670432197
1068567816.8080671501

result:

ok 3 numbers

Test #21:

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

input:

100
791419962 -705632280 273660 718513
-671760175 419287111 72247 757679
-947422084 -822503513 691371 616543
-680197423 560219273 767716 218740
-689664411 -17892517 547767 113677
789626230 -968725453 723426 604728
342150670 209416864 310319 617925
-62802591 -4429706 848985 580596
690294531 -30360571...

output:

372796359.8964574602 -441709616.7940758952
1155102638.8845349067

result:

ok 3 numbers

Test #22:

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

input:

100
-540015467 649074988 951067 68891
718279814 -99101273 820519 348689
-28878435 -806505436 742818 269493
-808672087 300314644 635568 285258
695995816 819112850 169301 649218
208680553 863644053 261219 793938
-495501106 939898998 206931 444340
-868445095 305629953 549675 743300
-76057590 711930803 ...

output:

-579117325.7460156282 -700064522.0995702744
1179476387.7165031742

result:

ok 3 numbers

Test #23:

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

input:

100
941750466 252686798 789771 244079
339557984 -358295465 694656 887091
-643348434 275235426 282746 838866
200832405 -903379495 826596 561415
315084105 -909868114 965863 674091
991949539 -293913017 44321 888543
-914326993 231398240 655237 371752
654991829 -613082042 900020 567550
614508174 14595723...

output:

435381577.1868479536 349150452.2460038299
1522214340.9718883871

result:

ok 3 numbers

Test #24:

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

input:

2
1 1 1 1
5 1 1 1

output:

3.0000000000 1.0000000000
2.8284271247

result:

ok 3 numbers

Test #25:

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

input:

5
3 4 5 1
17 4 7 1
10 -13 6 2
10 21 7 1
-7 4 1 1

output:

1.5000000000 4.0000000000
15.2315462117

result:

ok 3 numbers