QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712747 | #2950. Growing Some Oobleck | stavage | TL | 1ms | 3908kb | C++20 | 2.6kb | 2024-11-05 16:54:43 | 2024-11-05 16:54:43 |
Judging History
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