QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#712747#2950. Growing Some OobleckstavageTL 1ms3908kbC++202.6kb2024-11-05 16:54:432024-11-05 16:54:43

Judging History

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

  • [2024-11-05 16:54:43]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3908kb
  • [2024-11-05 16:54:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
#define int LL
#define double LD
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acosl(-1);
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
};
typedef Point Vector;
Point operator+(Point a, Point b) { return Point(a.x + b.x, a.y + b.y); }
Point operator-(Point a, Point b) { return Point(a.x - b.x, a.y - b.y); }
Point operator*(Point a, double p) { return Point(a.x * p, a.y * p); }
Point operator/(Point a, double p) { return Point(a.x / p, a.y / p); }
bool operator<(const Point &a, const Point &b) { return a.x < b.x || (a.x == b.x && a.y < b.y); }

struct Circle {
    double x, y, r, s;
    Circle(double x = 0, double y = 0, double r = 0, double s = 0) : x(x), y(y), r(r), s(s) {}
};
Circle read_C()
{
    Circle c;
    cin >> c.x >> c.y >> c.r >> c.s;
    return c;
}
double dis(Circle a, Circle b)
{
    return sqrtl((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
double ctime(Circle a, Circle b)
{
    return (dis(a, b) - a.r - b.r) / (a.s + b.s);
}

vector<Circle> v;
int merge(int k)
{
    Circle c;
    Circle now = v[k];
    int cnt = 0;
    for (int i = 0; i < v.size();) {
        if (dis(now, v[i]) - now.r - v[i].r <= 0) {
            c.r += (v[i].r * v[i].r);
            c.s = max(c.s, v[i].s);
            c.x += v[i].x;
            c.y += v[i].y;
            cnt++;
            swap(v[i], v[v.size() - 1]);
            v.pop_back();
        }
        else i++;
    }
    c.x /= cnt;
    c.y /= cnt;
    c.r = sqrtl(c.r);
    v.push_back(c);
    return cnt;
}
int n;
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        Circle x;
        x = read_C();
        v.push_back(x);
    }
    int l = -1, r = -1;
    while (v.size() > 1) {
        for (int i = 0; i < v.size(); i++) {
            for (int j = i + 1; j < v.size(); j++) {
                if (l == -1 || ctime(v[l], v[r]) > ctime(v[i], v[j])) {
                    l = i;
                    r = j;
                }
            }
        }
        double t = ctime(v[l], v[r]);
        for (int i = 0; i < v.size(); i++) {
            v[i].r += t * v[i].s;
        }
        while (merge(l) > 1) {
            l = v.size() - 1;
        }
    }
    cout << v[0].x << " " << v[0].y << "\n" << v[0].r << "\n";
}
signed main()
{
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    int _ = 1;
    while (_--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3908kb

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: -100
Time Limit Exceeded

input:

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

output:


result: