QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#699199#2950. Growing Some Ooblecknickbelov#WA 30ms7192kbC++204.0kb2024-11-02 04:59:102024-11-02 04:59:10

Judging History

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

  • [2024-11-02 04:59:10]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:7192kb
  • [2024-11-02 04:59:10]
  • 提交

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 = 1e-10;

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 d = INFINITY, t = 0;
    for (int i : rep(n)) {
        for (int j : rep(i)) {
            auto& c1 = circs[i], c2 = circs[j];
            ld d1 = (hypotl(c1.x - c2.x, c1.y - c2.y) - c1.r - c2.r);
            if (d1 <= d + EPSILON) {
                a = i; b = j;
                d = d1;
                t = d1 / (c1.s + c2.s);
            }
        }
    }
    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: 7132kb

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: 29ms
memory: 7128kb

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: 29ms
memory: 7096kb

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

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: 25ms
memory: 7192kb

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: 29ms
memory: 7180kb

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: 29ms
memory: 7096kb

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: -100
Wrong Answer
time: 30ms
memory: 7120kb

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.437500000000 0.687500000000
725.909913231704

result:

wrong answer 1st numbers differ - expected: '500.0000000', found: '500.4375000', error = '0.0008750'