QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#636351 | #4573. Global Warming | ucup-team2172 | AC ✓ | 426ms | 58180kb | C++14 | 5.2kb | 2024-10-12 23:31:32 | 2024-10-12 23:31:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 1e5 + 5;
const int maxq = 1e5 + 5;
int n, m, q;
int a[maxm], b[maxm], c[maxm], fa[maxm];
int px[maxn], py[maxn], pz[maxn], face[maxn];
vector<pair<int, pair<int, int> > > ed;
map<pair<int, int>, int> mp;
inline void addEdge(int p, int q, int i) {
if (p < q) swap(p, q);
if (mp.find(make_pair(p, q)) == mp.end()) mp[make_pair(p, q)] = i;
else {
int j = mp[make_pair(p, q)];
ed.push_back(make_pair(max(pz[p], pz[q]) - 1, make_pair(i, j)));
}
}
int h[maxq], p[maxq], ord[maxq];
long double ans[maxq];
inline int find(int u) { return (u == fa[u] ? u : (fa[u] = find(fa[u]))); }
class Data{
public:
long double s0, s1, s2;
Data(long double s0_ = 0, long double s1_ = 0, long double s2_ = 0): s0(s0_), s1(s1_), s2(s2_){}
inline Data &operator += (const Data &oth) {
s0 += oth.s0, s1 += oth.s1, s2 += oth.s2;
return *this;
}
inline long double eval(long double h) {
// printf("eval s0 = %Lf s1 = %Lf s2 = %Lf h = %Lf\n", s0, s1, s2, h);
return s0 + s1 * h + s2 * h * h;
}
} dat[maxm];
inline void merge(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
fa[u] = v;
dat[v] += dat[u];
// printf("v = %d dat = %Lf %Lf %Lf\n", v, dat[v].s0, dat[v].s1, dat[v].s2);
return;
}
vector<pair<pair<int, int>, Data> > vec;
inline long double area(long double xa, long double ya, long double za, long double xb, long double yb, long double zb, long double xc, long double yc, long double zc) {
long double x1 = xb - xa, y1 = yb - ya, z1 = zb - za,
x2 = xc - xa, y2 = yc - ya, z2 = zc - za;
long double s0 = y1 * z2 - y2 * z1, s1 = z1 * x2 - x1 * z2, s2 = x1 * y2 - x2 * y1;
return sqrt(s0 * s0 + s1 * s1 + s2 * s2) * 0.5;
}
inline void getsep(int i) {
// printf("getsep i = %d %d %d %d\n", i, pz[a[i]], pz[b[i]], pz[c[i]]);
if (pz[a[i]] == pz[c[i]]) {
long double s = area(px[a[i]], py[a[i]], pz[a[i]], px[b[i]], py[b[i]], pz[b[i]], px[c[i]], py[c[i]], pz[c[i]]);
vec.push_back(make_pair(make_pair(pz[c[i]] - 1, i),
Data(s, 0, 0)));
}
else {
long double r = 1.0 * (pz[b[i]] - pz[a[i]]) / (pz[c[i]] - pz[a[i]]);
long double xm = px[c[i]] * r + px[a[i]] * (1 - r),
ym = py[c[i]] * r + py[a[i]] * (1 - r),
zm = pz[c[i]] * r + pz[a[i]] * (1 - r);
if (pz[c[i]] != pz[b[i]]) {
long double sup = area(px[c[i]], py[c[i]], pz[c[i]], xm, ym, zm, px[b[i]], py[b[i]], pz[b[i]]);
long double s1 = sup / (pz[c[i]] - pz[b[i]]) / (pz[c[i]] - pz[b[i]]);
// printf("sup = %Lf %d\n", sup, pz[c[i]] - pz[b[i]]);
vec.push_back(make_pair(make_pair(pz[c[i]], i),
Data(1.0 * pz[c[i]] * pz[c[i]] * s1, -2.0 * pz[c[i]] * s1, s1)));
vec.push_back(make_pair(make_pair(pz[b[i]], i),
Data(-1.0 * pz[c[i]] * pz[c[i]] * s1 + sup, 2.0 * pz[c[i]] * s1, -s1)));
}
if (pz[a[i]] != pz[b[i]]) {
long double sdn = area(px[a[i]], py[a[i]], pz[a[i]], xm, ym, zm, px[b[i]], py[b[i]], pz[b[i]]);
long double s2 = sdn / (pz[b[i]] - pz[a[i]]) / (pz[b[i]] - pz[a[i]]);
// printf("sdn = %Lf %d\n", sdn, pz[b[i]] - pz[a[i]]);
vec.push_back(make_pair(make_pair(pz[b[i]], i),
Data(-1.0 * pz[a[i]] * pz[a[i]] * s2 + sdn, 2.0 * pz[a[i]] * s2, -s2)));
vec.push_back(make_pair(make_pair(pz[a[i]], i),
Data(1.0 * pz[a[i]] * pz[a[i]] * s2, -2.0 * pz[a[i]] * s2, s2)));
}
}
}
int main(){
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d%d%d", px + i, py + i, pz + i);
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
int tmp[3]; scanf("%d%d%d", tmp + 0, tmp + 1, tmp + 2);
--tmp[0], --tmp[1], --tmp[2];
sort(tmp, tmp + 3, [&] (const int &p, const int &q) { return pz[p] < pz[q]; });
a[i] = tmp[0], b[i] = tmp[1], c[i] = tmp[2];
face[a[i]] = face[b[i]] = face[c[i]] = i;
addEdge(a[i], b[i], i);
addEdge(b[i], c[i], i);
addEdge(a[i], c[i], i);
getsep(i);
}
sort(ed.begin(), ed.end(), [&] (const pair<int, pair<int, int> > &x, const pair<int, pair<int, int> > &y) { return x.first > y.first; });
scanf("%d", &q);
for (int i = 0; i < q; ++i) {
scanf("%d%d", h + i, p + i); --p[i];
ord[i] = i;
}
sort(ord, ord + q, [&] (const int &i, const int &j) { return h[i] > h[j]; });
sort(vec.begin(), vec.end(), [&] (const pair<pair<int, int>, Data> &x, const pair<pair<int, int>, Data> &y) { return x.first > y.first; });
for (int i = 0; i < m; ++i) fa[i] = i;
for (int it = 0, j = 0, k = 0; it < q; ++it) {
int i = ord[it];
// printf("query i = %d h = %d\n", i, h[i]);
for (; j < ed.size() && ed[j].first >= h[i]; ++j) {
// printf(" edge (%d %d)\n", ed[j].second.first, ed[j].second.second);
merge(ed[j].second.first, ed[j].second.second);
}
for (; k < vec.size() && vec[k].first.first >= h[i]; ++k) {
// printf(" area %d (%Lf %Lf %Lf)\n", vec[k].first.second, vec[k].second.s0, vec[k].second.s1, vec[k].second.s2);
dat[find(vec[k].first.second)] += vec[k].second;
}
int r = find(face[p[i]]);
// printf("r = %d\n", r);
if (pz[p[i]] > h[i]) ans[i] = dat[r].eval(h[i]);
else ans[i] = -1e9;
}
for (int i = 0; i < q; ++i) {
if (ans[i] < -1e6) puts("-1");
else printf("%.10Lf\n", ans[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 13000kb
input:
5 0 0 0 2 0 0 2 2 0 0 2 0 1 1 4 4 1 2 5 2 3 5 3 4 5 4 1 5 7 0 1 0 5 1 5 2 5 3 5 4 5 5 5
output:
-1 16.4924225025 9.2769876576 4.1231056256 1.0307764064 -1 -1
result:
ok 7 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 12956kb
input:
16 0 5 0 1 2 0 2 5 5 3 7 0 4 0 0 4 3 5 5 5 1 6 2 0 6 6 5 7 4 4 7 8 0 8 2 0 9 4 0 4 6 4 6 3 3 2 4 5 22 11 10 9 12 8 10 2 6 5 9 10 7 8 15 6 16 3 6 15 6 7 7 3 14 8 10 15 11 13 10 16 6 2 12 10 13 10 7 15 16 3 2 3 4 1 14 7 9 11 9 4 3 6 7 5 6 8 14 4 3 3 1 2 9 4 14 7 0 7 1 7 1 16 2 10 3 9 4 16 5 16
output:
120.4834053543 -1 93.9298952225 68.1819196635 40.9185614741 11.0674417909 -1
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 14224kb
input:
9 0 0 0 0 1 0 0 2 0 1 0 0 1 1 10 1 2 0 2 0 0 2 1 0 2 2 0 8 4 8 5 5 9 8 8 4 7 1 2 5 2 6 3 9 6 5 6 2 5 1 5 4 5 9 5 0 5 3 5 3 5 2 5
output:
0.3427719812 34.2771981210 16.7958270793 16.7958270793 21.9374067974
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 14320kb
input:
100 0 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 1 0 0 1 1 3 1 2 3 1 3 3 1 4 3 1 5 3 1 6 3 1 7 3 1 8 3 1 9 0 2 0 0 2 1 3 2 2 1 2 3 4 2 4 5 2 5 5 2 6 5 2 7 5 2 8 3 2 9 0 3 0 0 3 1 3 3 2 4 3 3 5 3 4 7 3 5 7 3 6 6 3 7 5 3 8 3 3 9 0 4 0 0 4 1 1 4 2 4 4 3 6 4 4 8 4 5 6 4 6 3 4 7 5 4 8 3 4 ...
output:
81.6704137546 183.3667939331 33.4906926470 183.3667939331 183.3667939331
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 333ms
memory: 58180kb
input:
49729 0 0 0 0 1234 0 0 2468 0 0 3702 0 0 4936 0 0 6170 0 0 7404 0 0 8638 0 0 9872 0 0 11106 0 0 12340 0 0 13574 0 0 14808 0 0 16042 0 0 17276 0 0 18510 0 0 19744 0 0 20978 0 0 22212 0 0 23446 0 0 24680 0 0 25914 0 0 27148 0 0 28382 0 0 29616 0 0 30850 0 0 32084 0 0 33318 0 0 34552 0 0 35786 0 0 3702...
output:
28336022114792.7899818420 -1 9067597268.2016000599 29490770935284.6284751892 21397921724095.2214927673 -1 414425634047.6375958323 -1 -1 -1 -1 -1 30771157933943.6548900604 -1 25468403653000.2862834930 -1 -1 16769145554603.7865562439 -1 -1 31149212820079.1136360168 31077512125207.3616275787 -1 6772280...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 391ms
memory: 54128kb
input:
49729 0 0 0 0 1234 0 0 2468 0 0 3702 0 0 4936 0 0 6170 0 0 7404 0 0 8638 0 0 9872 0 0 11106 0 0 12340 0 0 13574 0 0 14808 0 0 16042 0 0 17276 0 0 18510 0 0 19744 0 0 20978 0 0 22212 0 0 23446 0 0 24680 0 0 25914 0 0 27148 0 0 28382 0 0 29616 0 0 30850 0 0 32084 0 0 33318 0 0 34552 0 0 35786 0 0 3702...
output:
29353956709678.4136199951 31503581108233.6083736420 2451504799.0853413376 30277327205891.4484691620 30263230103493.7525749207 31519100793321.2626934052 31472715345694.0055446625 26006398827719.2323036194 30685636802105.0305080414 21445819885897.9458255768 17801360715783.2468528748 26153683091551.467...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 341ms
memory: 41480kb
input:
49729 0 0 0 0 1234 0 0 2468 0 0 3702 0 0 4936 0 0 6170 0 0 7404 0 0 8638 0 0 9872 0 0 11106 0 0 12340 0 0 13574 0 0 14808 0 0 16042 0 0 17276 0 0 18510 0 0 19744 0 0 20978 0 0 22212 0 0 23446 0 0 24680 0 0 25914 0 0 27148 0 0 28382 0 0 29616 0 0 30850 0 0 32084 0 0 33318 0 0 34552 0 0 35786 0 0 3702...
output:
572960766753.5639795065 333954833128.7901468277 781430007202.2610054612 485385379872.3814913034 551112725934.5882058144 167358330713.0826252103 925545375390.3372147679 884146260755.7528733611 868595978493.3022571206 499588429515.9451282322 744105035354.9899690747 508001836416.0402140617 777023838275...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 330ms
memory: 57880kb
input:
49729 0 0 0 0 1234 0 0 2468 0 0 3702 0 0 4936 0 0 6170 0 0 7404 0 0 8638 0 0 9872 0 0 11106 0 0 12340 0 0 13574 0 0 14808 0 0 16042 0 0 17276 0 0 18510 0 0 19744 0 0 20978 0 0 22212 0 0 23446 0 0 24680 0 0 25914 0 0 27148 0 0 28382 0 0 29616 0 0 30850 0 0 32084 0 0 33318 0 0 34552 0 0 35786 0 0 3702...
output:
897647.2186110494 41601577.1805878018 57963769155.7551694512 2006308.5490500588 66648786362.2485023104 72258674159.1914519593 72258674159.1914519593 122697223.2080058617 74912964693.4198815748 66648786362.2485023104 66648786362.2485023104 74912964693.4198815748 44587741917.2225577161 29074547.315690...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 14424kb
input:
12 0 0 0 0 5 0 5 5 0 5 0 0 1 1 2 1 4 2 4 4 2 4 1 2 2 2 0 2 3 0 3 3 0 3 2 0 18 10 9 11 11 6 7 5 6 10 5 8 4 12 11 9 6 2 1 10 9 5 8 5 9 1 5 4 8 7 12 6 5 1 8 9 12 10 11 6 8 4 3 7 2 6 12 7 11 3 7 8 2 7 3 1 0 5
output:
53.6656314600
result:
ok found '53.6656315', expected '53.6656315', error '0.0000000'
Test #10:
score: 0
Accepted
time: 4ms
memory: 12708kb
input:
12 0 0 0 0 5 0 5 5 0 5 0 0 1 1 2 1 4 2 4 4 2 4 1 2 2 2 4 2 3 4 3 3 4 3 2 4 18 10 9 11 11 6 7 5 6 10 5 8 4 12 11 9 6 2 1 10 9 5 8 5 9 1 5 4 8 7 12 6 5 1 8 9 12 10 11 6 8 4 3 7 2 6 12 7 11 3 7 8 2 7 3 1 0 5
output:
54.6656314600
result:
ok found '54.6656315', expected '54.6656315', error '0.0000000'
Test #11:
score: 0
Accepted
time: 417ms
memory: 56312kb
input:
50000 1000000 0 0 -499999 866025 0 -500000 -866025 0 916495 24153 20321 315147 394537 769870 651467 -179658 360140 233942 -76261 740341 838791 87259 126557 303017 392128 779543 941754 -6365 19430 124786 -492497 772546 -217751 -238771 297571 -23711 323594 636099 275839 -188254 736640 928586 29943 345...
output:
43430624283954.1610527039 12858380405517.4920158386 93482365765.1163754463 43321845735814.3461494446 13336447877237.2140369415 17404343997.3879560083 34467363242303.3159027100 43405094547561.5905189514 39131002840237.2582397461 43393693093480.5080947876 806324082489.1204773188 36819948840038.8339233...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 410ms
memory: 55024kb
input:
50000 1000000 0 0 -499999 866025 0 -500000 -866025 0 602988 91211 216221 455493 -119881 429853 -399458 274661 465649 -291227 492885 333531 305005 -199848 590862 117889 393387 758345 41752 476626 673156 -259925 -672385 311200 80905 256085 768625 -462678 6550 279723 451465 118984 371649 831927 -20281 ...
output:
2322831875036.9456405640 25855254818251.7308368683 25786991781147.4878463745 2942524730858.3229572773 15254374353.8633832932 22617750383708.0957622528 15515939596317.9533996582 16179419706100.7089443207 22057567140769.4745731354 9240282644053.2330112457 26062087530223.2227096558 25817683944141.07281...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 426ms
memory: 56664kb
input:
50000 1000000 0 0 -499999 866025 0 -500000 -866025 0 -406181 -463113 5565 360070 -254117 327382 -435002 -370999 150939 -432026 -264882 736215 -431996 -315399 763809 -34186 74054 210200 -495547 600420 422265 -442146 -482250 335082 263246 -379485 810689 -481286 373221 471520 -184475 -578243 257916 804...
output:
1796860254418.8200025558 242290432739284.3957061768 382427698314815.8914184570 16895448115472.1242828369 175161422.5678363184 75351167646370.3004455566 203278352090659.0688323975 119637497847007.9544372559 1480483568469.4770009518 126508943777914.2019653320 240306734905327.2893371582 52766516713336....
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 401ms
memory: 55824kb
input:
50000 14233 -482924 503223 -619853 42191 836937 933219 -630695 981538 571855 -506938 928685 659572 -89936 331112 396383 -935548 714968 -110061 -834487 204893 -327590 159339 192510 -773712 -294863 371202 716312 804785 562164 124500 -362150 635977 383472 -527493 368927 283452 827395 515767 -9790 -3693...
output:
-1 11677533560170376.7226562500 -1 2327625177955293.8281250000 10593333095221017.0761718750 12710524468264703.3066406250 -1 2019951545369947.1689453125 -1 12445254039687682.4433593750 9559056375926237.6455078125 11419834997464115.5263671875 -1 -1 12690908030987137.8574218750 110400643795.3405723572 ...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 420ms
memory: 55616kb
input:
50000 -884634 740598 254245 -848157 107291 379205 814379 -969178 47711 266076 562979 729407 429003 -174495 625696 -85197 -456582 198461 -817626 -664002 629444 -865129 -789609 237813 737831 724197 617606 -621008 997403 210152 -849460 946458 817676 567198 934117 897456 883783 -316320 844007 -837482 -1...
output:
15574462096016379.9550781250 10053475564194190.6767578125 15575656264873924.5976562500 15578451364341851.7578125000 15475194319450041.1699218750 15583907372907838.8642578125 14918882475507764.0820312500 15573693366188284.6386718750 15583166533434626.4140625000 15304002013976189.2216796875 1522710213...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 413ms
memory: 57084kb
input:
50000 547614 -545758 429052 227222 -204199 714473 -67322 415880 921974 -744631 -943094 184202 -859827 785569 226236 -614105 -629950 477041 527507 -10999 798771 -122047 -781292 568327 -78172 745536 478104 -495749 -687586 537199 -539763 800565 356415 -315477 -720985 375379 -697970 -694551 384093 22027...
output:
6791253380611264.6733398438 6444948610720401.9497070312 6906763735824260.4404296875 6698124103036643.2905273438 6404745518809350.5478515625 3935529254.3356781006 291733933253848.0504455566 6905207700103069.2080078125 6573585355062345.2534179688 1091222950371.5237227678 6710915828362307.7187500000 69...
result:
ok 100000 numbers