QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#660539 | #2950. Growing Some Oobleck | enze114514 | AC ✓ | 2ms | 3960kb | C++20 | 3.3kb | 2024-10-20 11:56:38 | 2024-10-20 11:56:39 |
Judging History
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;
}
详细
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