QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699201#2950. Growing Some Ooblecknickbelov#AC ✓37ms7192kbC++204.0kb2024-11-02 05:04:452024-11-02 05:04:46

Judging History

This is the latest submission verdict.

  • [2024-11-02 05:04:46]
  • Judged
  • Verdict: AC
  • Time: 37ms
  • Memory: 7192kb
  • [2024-11-02 05:04:45]
  • Submitted

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
ostream_iterator<T> oit(const string &s = " "){ return ostream_iterator<T>(cout,s.c_str()); }
inline auto rep(int l, int r) { return views::iota(min(l, r), r); }
inline auto rep(int n) { return rep(0, n); }
inline auto rep1(int l, int r) { return rep(l, r + 1); }
inline auto rep1(int n) { return rep(1, n + 1); }
inline auto per(int l, int r) { return rep(l, r) | views::reverse; }
inline auto per(int n) { return per(0, n); }
inline auto per1(int l, int r) { return per(l, r + 1); }
inline auto per1(int n) { return per(1, n + 1); }
#define A(a) begin(a),end(a)
inline auto len = ranges::ssize;

struct chash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
template<typename T, typename U> using pb_map = gp_hash_table<T, U, chash>;
template<typename T> using pb_set = gp_hash_table<T, null_type, chash>;
#define K first
#define V second

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vii = vector<vector<int>>;
typedef vector<ll> vll;
using pll = pair<ll,ll>;
using pii = pair<int,int>;
constexpr ld EPSILON = 0;

constexpr ll NN = 2e5, M = 1000000007, L = 20;

ll f1[NN], f2[NN];
ll inv(ll a, ll b=M) { return 1 < a ? b - inv(b % a, a) * b / a : 1; } // inv a mod b
ll choose(ll n, ll k) { return f1[n] * f2[k] % M * f2[n - k] % M; } // n choose k
int n;
struct Circle {
    ld x, y, r, s;
};

vector<Circle> circs;

void del(int i) {
    swap(circs[i], circs[n-1]);
    --n;
    circs.pop_back();
}

void expand(ld t) {
    for (auto& c : circs) {
        c.r += c.s * t;
    }
}

void cascade(int i) {
    ld sx = 0, sy = 0, sa = 0, ms = 0;
    int cnt = 0;
    auto& c = circs[i];
    vector<int> marked;
    for (int j : rep(n)) {
        auto& c2 = circs[j];
        if (hypotl(c.x-c2.x, c.y-c2.y) <= c.r + c2.r + EPSILON) {
            cnt++;
            sx += c2.x;
            sy += c2.y;
            sa = hypotl(sa, c2.r);
            ms = max(ms, c2.s);
            marked.push_back(j);
        }
    }
    if (marked.size() <= 1) return;
    c.x = sx / cnt;
    c.y = sy / cnt;
    c.r = sa;
    c.s = ms;
    reverse(A(marked));
    for (int x : marked) {
        if (x == i) continue;
        if (i == n-1) {
            i = x;
        }
        del(x);
    }
    cascade(i);
}

void mrg() {
    int a, b;
    ld t = INFINITY;
    for (int i : rep(n)) {
        for (int j : rep(i)) {
            auto& c1 = circs[i], c2 = circs[j];
            ld t1 = (hypotl(c1.x - c2.x, c1.y - c2.y) - c1.r - c2.r) / (c1.s + c2.s);
            if (t1 < t) {
                a = i; b = j;
                t = t1;
            }
        }
    }
    expand(t);
    auto& c1 = circs[a], c2 = circs[b];
    c1.x = (c1.x + c2.x) / 2;
    c1.y = (c1.y + c2.y) / 2;
    c1.r = hypotl(c1.r, c2.r);
    c1.s = max(c1.s, c2.s);
    if (a == n-1) a = b;
    del(b);
    cascade(a);
}

void run()
{
    cin >> n;
    circs.resize(n);
    for (auto& c : circs) {
        cin >> c.x >> c.y >> c.r >> c.s;
    }
    while (circs.size() > 1) mrg();
    cout << fixed << setprecision(12) << circs[0].x << " " << circs[0].y << endl;
    cout << circs[0].r << endl;
}

int main()
{
    //KING OF THE WORLD...... U.W.T.B
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    f1[0] = 1;
    f2[0] = 1;
    for (int i = 1; i < NN; i++) {
        f1[i] = f1[i - 1] * i % M;
        f2[i] = inv(f1[i], M);
    }
    int t=1; while(t--) run();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 30ms
memory: 7052kb

input:

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

output:

16.500000000000 6.000000000000
10.440306508911

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 26ms
memory: 7132kb

input:

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

output:

1.187500000000 -3.125000000000
7.616776813122

result:

ok 3 numbers

Test #3:

score: 0
Accepted
time: 26ms
memory: 7048kb

input:

2
-1000000000 0 1 1
1000000000 0 1 1

output:

0.000000000000 0.000000000000
1414213562.373095048824

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 29ms
memory: 7120kb

input:

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

output:

225000000.000000000000 0.000000000000
1673350486.960810329299

result:

ok 3 numbers

Test #5:

score: 0
Accepted
time: 30ms
memory: 7100kb

input:

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

output:

-137500000.000000000000 500000000.000000000000
2074241311.012399946107

result:

ok 3 numbers

Test #6:

score: 0
Accepted
time: 25ms
memory: 7068kb

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.589843750000 1.000000000000
13239.142792141766

result:

ok 3 numbers

Test #7:

score: 0
Accepted
time: 30ms
memory: 7180kb

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.000000000000 -10640.589843750000
13239.142792141766

result:

ok 3 numbers

Test #8:

score: 0
Accepted
time: 26ms
memory: 7192kb

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.000000000000 0.000000000000
725.258698493373

result:

ok 3 numbers

Test #9:

score: 0
Accepted
time: 29ms
memory: 7056kb

input:

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

output:

13.625000000000 5.500000000000
11.229147340738

result:

ok 3 numbers

Test #10:

score: 0
Accepted
time: 30ms
memory: 7108kb

input:

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

output:

13.625000000000 5.500000000000
11.245832561442

result:

ok 3 numbers

Test #11:

score: 0
Accepted
time: 26ms
memory: 7080kb

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.000000000000 10.000000000000
25.648610872120

result:

ok 3 numbers

Test #12:

score: 0
Accepted
time: 30ms
memory: 7136kb

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.000000000000 261.249085504811
375.568946911709

result:

ok 3 numbers

Test #13:

score: 0
Accepted
time: 37ms
memory: 7116kb

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.153564453125 107695.578613281250
84684.981560490749

result:

ok 3 numbers

Test #14:

score: 0
Accepted
time: 30ms
memory: 7180kb

input:

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

output:

0.000000000000 250000000.000000000000
1457737973.711369821685

result:

ok 3 numbers

Test #15:

score: 0
Accepted
time: 30ms
memory: 7096kb

input:

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

output:

250000000.000000000000 250000000.000000000000
1414185636.997804428916

result:

ok 3 numbers

Test #16:

score: 0
Accepted
time: 36ms
memory: 7120kb

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.458007684676 752427048.448427264055
940126064.811280636524

result:

ok 3 numbers

Test #17:

score: 0
Accepted
time: 34ms
memory: 7100kb

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.397315629321 266951144.242265496432
1209296596.114549955353

result:

ok 3 numbers

Test #18:

score: 0
Accepted
time: 37ms
memory: 7084kb

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.461106631497 170910810.394741422599
1440508744.012454642216

result:

ok 3 numbers

Test #19:

score: 0
Accepted
time: 37ms
memory: 7104kb

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.449379433529 639893986.290879567503
1135881519.562323578633

result:

ok 3 numbers

Test #20:

score: 0
Accepted
time: 33ms
memory: 7128kb

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.122212473536 -300376760.267043219676
1068567816.808067150065

result:

ok 3 numbers

Test #21:

score: 0
Accepted
time: 34ms
memory: 7040kb

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.896457460185 -441709616.794075895246
1155102638.884534906596

result:

ok 3 numbers

Test #22:

score: 0
Accepted
time: 34ms
memory: 7036kb

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.746015628160 -700064522.099570274353
1179476387.716503174044

result:

ok 3 numbers

Test #23:

score: 0
Accepted
time: 34ms
memory: 7068kb

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.186847953650 349150452.246003829874
1522214340.971888387110

result:

ok 3 numbers

Test #24:

score: 0
Accepted
time: 29ms
memory: 7184kb

input:

2
1 1 1 1
5 1 1 1

output:

3.000000000000 1.000000000000
2.828427124746

result:

ok 3 numbers

Test #25:

score: 0
Accepted
time: 25ms
memory: 7096kb

input:

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

output:

1.500000000000 4.000000000000
15.231546211728

result:

ok 3 numbers