QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54283 | #4573. Global Warming | not_so_organic# | AC ✓ | 407ms | 45952kb | C++23 | 3.8kb | 2022-10-07 19:10:02 | 2022-10-07 19:10:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using D = long double;
struct P{
LL x, y, z;
bool operator < (const P& p) const {
return z == p.z ? (
y == p.y ? x > p.x : y > p.y
) : z > p.z;
}
};
struct F{
D a, b, c;
F(D a = 0, D b = 0, D c = 0) : a(a), b(b), c(c) {
}
F(const P& p){
a = p.x;
b = p.y;
c = p.z;
}
F operator * (D k) const {
return {a * k, b * k, c * k};
}
F operator + (const F& f) const {
return {a + f.a, b + f.b, c + f.c};
}
F operator - (const F& f) const {
return {a - f.a, b - f.b, c - f.c};
}
F& operator += (const F& f) {
a += f.a;
b += f.b;
c += f.c;
return *this;
}
F& operator -= (const F& f) {
a -= f.a;
b -= f.b;
c -= f.c;
return *this;
}
D operator()(D x) {
return (a * x + b) * x + c;
}
F cross(const F& f) const {
return {
a * f.b - b * f.a,
b * f.c - c * f.b,
c * f.a - a * f.c
};
}
D norm() const{
return sqrt(a * a + b * b + c * c);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
int n;
cin >> n;
vector<P> p(n);
for (auto& [x, y, z] : p)
cin >> x >> y >> z;
int m;
cin >> m;
vector t(m, vector<int>(3));
vector df(m, vector<F>(3));
vector G(n, vector<vector<int>>(3));
for (int i = 0; i < m; i += 1) {
for (int& tj : t[i]) {
cin >> tj;
tj -= 1;
}
sort(t[i].begin(), t[i].end(), [&](int x, int y) {
return p[x] < p[y];
});
vector<F> tp(3);
for (int j = 0; j < 3; j += 1) tp[j] = p[t[i][j]];
D s = (tp[1] - tp[0]).cross(tp[2] - tp[0]).norm() / 2;
if (tp[0].c == tp[2].c)
df[i][0].c = s;
else if (tp[0].c == tp[1].c) {
D dh = tp[1].c - tp[2].c;
D a = s / (dh * dh);
df[i][1] = {-a, 2 * a * tp[2].c, s - a * tp[2].c * tp[2].c};
df[i][2] = {0, 0, s};
df[i][2] -= df[i][1];
}
else if (tp[1].c == tp[2].c) {
D dh = tp[0].c - tp[1].c;
D a = s / (dh * dh);
df[i][0] = {a, -2 * a * tp[0].c, a * tp[0].c * tp[0].c};
df[i][1] = {0, 0, s};
df[i][1] -= df[i][0];
}
else {
D h1 = tp[0].c - tp[1].c;
D h2 = tp[1].c - tp[2].c;
F f = tp[0] + (tp[2] - tp[0]) * (h1 / (h1 + h2));
D s1 = (tp[1] - tp[0]).cross(f - tp[0]).norm() / 2;
D s2 = (tp[1] - tp[2]).cross(f - tp[2]).norm() / 2;
D a1 = s1 / (h1 * h1);
D a2 = s2 / (h2 * h2);
df[i][0] = {a1, -2 * a1 * tp[0].c, a1 * tp[0].c * tp[0].c};
df[i][1] = {-a2, 2 * a2 * tp[2].c, s - a2 * tp[2].c * tp[2].c};
df[i][2] = {0, 0, s};
df[i][2] -= df[i][1];
df[i][1] -= df[i][0];
}
for (int j = 0; j < 3; j += 1)
G[t[i][j]][j].push_back(i);
}
int q;
cin >> q;
vector<LL> h(q);
vector<int> pq(q), f(n), pv(n + q), qv(q);
vector<vector<int>> Q(n);
for (int i = 0; i < q; i += 1) {
cin >> h[i] >> pq[i];
qv[i] = i;
pv[n + i] = n + i;
pq[i] -= 1;
Q[pq[i]].push_back(i);
}
vector<D> ans(q, -1);
vector<F> cf(n);
for (int i = 0; i < n; i += 1)
pv[i] = f[i] = i;
function<int(int)> ff = [&](int u) {
return f[u] == u ? u : f[u] = ff(f[u]);
};
sort(pv.begin(), pv.end(), [&](int x, int y){
LL px = x >= n ? h[x - n] : p[x].z;
LL py = y >= n ? h[y - n] : p[y].z;
return px != py ? px > py : x > y;
});
for (int i : pv) {
if (i < n) {
int u = i;
for (int j = 0; j < 3; j += 1) {
for (int x : G[i][j]) {
for (int y = 0; y < j; y += 1) {
int v = t[x][y];
int fu = ff(u), fv = ff(v);
if (fu != fv) {
f[fu] = fv;
cf[fv] += cf[fu];
}
}
int fu = ff(u);
cf[fu] += df[x][j];
}
}
}
else {
i -= n;
if (h[i] < p[pq[i]].z) {
int u = ff(pq[i]);
ans[i] = cf[u](h[i]);
}
i += n;
}
}
for (D d : ans)
if (d < -0.9) cout << "-1\n";
else cout << d << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 3708kb
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.49242250247064219860 9.27698765763973623617 4.12310562561766054922 1.03077640640441513774 -1 -1
result:
ok 7 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3708kb
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.48340535430632507186 -1 93.92989522248478349159 68.18191966353693998087 40.91856147414833069081 11.06744179092106980522 -1
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 3856kb
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.34277198120999605863 34.27719812099960574464 16.79582707928980681543 16.79582707928980681543 21.93740679743974767747
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 2ms
memory: 3768kb
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.67041375455158742219 183.36679393306701510435 33.49069264698641297529 183.36679393306701510435 183.36679393306701510435
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 298ms
memory: 44564kb
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.79007530212402343750 -1 9067597268.20159996673464775085 29490770935284.62855911254882812500 21397921724095.22158241271972656250 -1 414425634047.63759446144104003906 -1 -1 -1 -1 -1 30771157933943.65496063232421875000 -1 25468403653000.28624153137207031250 -1 -1 16769145554603.786490440...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 379ms
memory: 44736kb
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.41348075866699218750 31503581108233.60822296142578125000 2451504799.08534144610166549683 30277327205891.44835090637207031250 30263230103493.75245857238769531250 31519100793321.26255035400390625000 31472715345694.00540542602539062500 26006398827719.23224639892578125000 30685636802105.0...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 381ms
memory: 45952kb
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.56390643119812011719 333954833128.79015082120895385742 781430007202.26097732782363891602 485385379872.38139396905899047852 551112725934.58813095092773437500 167358330713.08261156082153320312 925545375390.33722335100173950195 884146260755.75288367271423339844 868595978493.302268505096435...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 378ms
memory: 44612kb
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.21861104938216158189 41601577.18058780183127964847 57963769155.75516934320330619812 2006308.54905005876935319975 66648786362.24849710613489151001 72258674159.19144428521394729614 72258674159.19144428521394729614 122697223.20800586161203682423 74912964693.41987413913011550903 66648786362.24849...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 1ms
memory: 3700kb
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.66563145999495271221
result:
ok found '53.6656315', expected '53.6656315', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3876kb
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.66563145999495271221
result:
ok found '54.6656315', expected '54.6656315', error '0.0000000'
Test #11:
score: 0
Accepted
time: 367ms
memory: 45616kb
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.15934753417968750000 12858380405517.49036598205566406250 93482365765.11637914180755615234 43321845735814.34445571899414062500 13336447877237.21238803863525390625 17404343997.38795579969882965088 34467363242303.31440734863281250000 43405094547561.58883285522460937500 39131002840237.256...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 407ms
memory: 45736kb
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.94566321372985839844 25855254818251.73069763183593750000 25786991781147.48773765563964843750 2942524730858.32297587394714355469 15254374353.86338156461715698242 22617750383708.09581947326660156250 15515939596317.95342445373535156250 16179419706100.70890331268310546875 22057567140769.47...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 393ms
memory: 44980kb
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.82000148296356201172 242290432739284.39671325683593750000 382427698314815.89276123046875000000 16895448115472.12430000305175781250 175161422.56783631001599133015 75351167646370.30064392089843750000 203278352090659.06983947753906250000 119637497847007.95452117919921875000 1480483568469....
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 294ms
memory: 45368kb
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.77539062500000000000 -1 2327625177955293.61914062500000000000 10593333095221017.03125000000000000000 12710524468264703.49414062500000000000 -1 2019951545369946.87890625000000000000 -1 12445254039687682.56933593750000000000 9559056375926237.57812500000000000000 11419834997464115....
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 368ms
memory: 44820kb
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.91308593750000000000 10053475564194189.83496093750000000000 15575656264873924.56054687500000000000 15578451364341851.72851562500000000000 15475194319450041.02343750000000000000 15583907372907838.84863281250000000000 14918882475507763.79394531250000000000 15573693366188284.595703125...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 371ms
memory: 45108kb
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.56933593750000000000 6444948610720401.81542968750000000000 6906763735824260.35595703125000000000 6698124103036643.17919921875000000000 6404745518809350.40478515625000000000 3935529254.33567869663238525391 291733933253848.05087280273437500000 6905207700103069.12353515625000000000 657...
result:
ok 100000 numbers