QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#376318 | #4573. Global Warming | InfinityNS | AC ✓ | 424ms | 166528kb | C++14 | 4.0kb | 2024-04-04 04:12:31 | 2024-04-04 04:12:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ldb long double
#define pb push_back
struct p3{
ldb x,y,z;
p3():x(0),y(0),z(0){}
p3(ldb a,ldb b,ldb c):x(a),y(b),z(c){}
p3 cross(p3 p) {
return p3(y*p.z-z*p.y, z*p.x-x*p.z, x*p.y-y*p.x);
}
};
p3 operator + (p3 a,p3 b){return p3(a.x+b.x,a.y+b.y,a.z+b.z);}
p3 operator - (p3 a,p3 b){return p3(a.x-b.x,a.y-b.y,a.z-b.z);}
p3 operator * (p3 a,ldb b){return p3(a.x*b,a.y*b,a.z*b);}
p3 operator / (p3 a,ldb b){return p3(a.x/b,a.y/b,a.z/b);}
ldb dot(p3 a,p3 b){return a.x*b.x+a.y*b.y+a.z*b.z;}
ldb abs(p3 a){return sqrt(dot(a,a));}
const int N=100050;
int x[N],y[N],z[N];
int myFace[N];
const int M=1e6+50;
vector<pair<int,int>> Edge[M];
vector<pair<int,array<ldb,3>>> Formula[M];
vector<pair<int,int>> Qs[M];
map<pair<int,int>,int> edg;
void Check(int i,int a,int b){
if(a>b)swap(a,b);
if(edg[{a,b}]){
Edge[max(z[a],z[b])].pb({i,edg[{a,b}]});
}
edg[{a,b}]=i;
}
int p[N];
ldb coef[N][3];
int Find(int x){return p[x]==x?x:p[x]=Find(p[x]);}
void Union(int x,int y){
x=Find(x);
y=Find(y);
if(x==y)return;
for(int i=0;i<3;i++){
coef[y][i]+=coef[x][i];
}
p[x]=y;
}
void AddFormula(int i,int z,ldb a,ldb b,ldb c){
Formula[z].pb({i,{a,b,c}});
}
void AddTriangle(int i,p3 A,p3 B,p3 C){
ldb area=abs((B-A).cross(C-A))/2;
ldb hmax=max({A.z,B.z,C.z});
ldb hmin=min({A.z,B.z,C.z});
if(A.z<B.z)swap(A,B);
if(B.z<C.z)swap(B,C);
if(A.z<B.z)swap(A,B);
//printf("triangle area: %lf, hmax:%lf, hmin:%lf\n",area,hmax,hmin);
if(round(A.z)==round(B.z)){
ldb ml=area/(hmax-hmin)/(hmax-hmin);
ldb a=area-hmin*hmin*ml;
ldb b=2*hmin*ml;
ldb c=-ml;
//printf("%lf = %lf\n",area,a+hmin*b+hmin*hmin*c);
AddFormula(i,round(hmax),a,b,c);
AddFormula(i,round(hmin),-a,-b,-c);
}else{
ldb ml=area/(hmax-hmin)/(hmax-hmin);
ldb a=hmax*hmax*ml;
ldb b=-2*hmax*ml;
ldb c=ml;
//printf("%lf = %lf\n",area,a+hmin*b+hmin*hmin*c);
AddFormula(i,round(hmax),a,b,c);
AddFormula(i,round(hmin),-a,-b,-c);
}
}
ldb ans[N];
int main(){
int n;
scanf("%i",&n);
for(int i=1;i<=n;i++){
scanf("%i %i %i",&x[i],&y[i],&z[i]);
}
int m;
scanf("%i",&m);
ldb totalArea=0;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%i %i %i",&a,&b,&c);
Check(i,a,b);
Check(i,b,c);
Check(i,c,a);
myFace[a]=i;
myFace[b]=i;
myFace[c]=i;
int mxz=max({z[a],z[b],z[c]});
int mnz=min({z[a],z[b],z[c]});
p3 A=p3(x[a],y[a],z[a]);
p3 B=p3(x[b],y[b],z[b]);
p3 C=p3(x[c],y[c],z[c]);
ldb area=abs((B-A).cross(C-A))/2;
totalArea+=area;
//printf("face %i: area:%lf\n",i,area);
if(mxz==mnz){
AddFormula(i,mxz,area,0,0);
}else{
int mid=0;
if(z[a]!=mnz && z[a]!=mxz)mid=a;
if(z[b]!=mnz && z[b]!=mxz)mid=b;
if(z[c]!=mnz && z[c]!=mxz)mid=c;
if(mid){
if(z[a]<z[b])swap(a,b);
if(z[b]<z[c])swap(b,c);
if(z[a]<z[b])swap(a,b);
A=p3(x[a],y[a],z[a]);
B=p3(x[b],y[b],z[b]);
C=p3(x[c],y[c],z[c]);
p3 M=C+(A-C)*(z[b]-z[c])/(z[a]-z[c]);
ldb area2=abs((M-B).cross(A-B))/2;
AddTriangle(i,A,B,M);
AddFormula(i,z[b],area2,0,0);
AddTriangle(i,B,M,C);
AddFormula(i,z[c],-area2,0,0);
}else{
AddTriangle(i,A,B,C);
}
AddFormula(i,mnz,area,0,0);
}
}
//printf("total area: %lf\n",totalArea);
for(int i=1;i<=m;i++)p[i]=i;
int q;
scanf("%i",&q);
for(int i=1;i<=q;i++){
int h,p;
scanf("%i %i",&h,&p);
Qs[h].pb({i,p});
}
for(int i=M-1;i>=0;i--){
for(auto qu:Qs[i]){
if(z[qu.second]<=i){
ans[qu.first]=-1;
}else{
int x=Find(myFace[qu.second]);
ans[qu.first]=coef[x][0]+coef[x][1]*i+coef[x][2]*i*i;
}
}
for(auto e:Edge[i]){
Union(e.first,e.second);
}
for(auto f:Formula[i]){
//printf("%i: Add %i formula %lf %lf %lf\n",i,f.first,f.second[0],f.second[1],f.second[2]);
int x=Find(f.first);
for(int j=0;j<3;j++){
coef[x][j]+=f.second[j];
}
}
}
for(int i=1;i<=q;i++)printf("%.12Lf\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 8ms
memory: 75648kb
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.000000000000 16.492422502471 9.276987657640 4.123105625618 1.030776406404 -1.000000000000 -1.000000000000
result:
ok 7 numbers
Test #2:
score: 0
Accepted
time: 8ms
memory: 75592kb
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.483405354306 -1.000000000000 93.929895222485 68.181919663537 40.918561474148 11.067441790921 -1.000000000000
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 11ms
memory: 77608kb
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.342771981210 34.277198121000 16.795827079290 16.795827079290 21.937406797440
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 8ms
memory: 77688kb
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.670413754552 183.366793933067 33.490692646986 183.366793933067 183.366793933067
result:
ok 5 numbers
Test #5:
score: 0
Accepted
time: 375ms
memory: 166528kb
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.790248870850 -1.000000000000 9067597268.201599899679 29490770935284.628692626953 21397921724095.221580505371 -1.000000000000 414425634047.637593626976 -1.000000000000 -1.000000000000 -1.000000000000 -1.000000000000 -1.000000000000 30771157933943.655076980591 -1.000000000000 2546840365...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 398ms
memory: 166520kb
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.413946151733 31503581108233.608379364014 2451504799.085341529921 30277327205891.448860168457 30263230103493.752948760986 31519100793321.262689590454 31472715345694.005632400513 26006398827719.232589721680 30685636802105.030897140503 21445819885897.945796966553 17801360715783.246788024...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 298ms
memory: 122808kb
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.564018011093 333954833128.790180921555 781430007202.261334180832 485385379872.381571710110 551112725934.588239729404 167358330713.082653641701 925545375390.337860465050 884146260755.753469765186 868595978493.302853941917 499588429515.945243149996 744105035354.990193545818 508001836416.0...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 262ms
memory: 132796kb
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.218611049382 41601577.180587801828 57963769155.755166143179 2006308.549050058764 66648786362.248491749167 72258674159.191434785724 72258674159.191434785724 122697223.208005862398 74912964693.419860236347 66648786362.248491749167 66648786362.248491749167 74912964693.419860236347 44587741917.22...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 12ms
memory: 75628kb
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.665631459995
result:
ok found '53.6656315', expected '53.6656315', error '0.0000000'
Test #10:
score: 0
Accepted
time: 12ms
memory: 75652kb
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.665631459995
result:
ok found '54.6656315', expected '54.6656315', error '0.0000000'
Test #11:
score: 0
Accepted
time: 399ms
memory: 156932kb
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.160732269287 12858380405517.491431236267 93482365765.116380602121 43321845735814.345722198486 13336447877237.213489532471 17404343997.387955637649 34467363242303.315526962280 43405094547561.590198516846 39131002840237.257846832275 43393693093480.507640838623 806324082489.120477795601 ...
result:
ok 100000 numbers
Test #12:
score: 0
Accepted
time: 424ms
memory: 158552kb
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.945660114288 25855254818251.730531692505 25786991781147.487567901611 2942524730858.322987556458 15254374353.863383531570 22617750383708.095426559448 15515939596317.953077316284 16179419706100.708585739136 22057567140769.474245071411 9240282644053.232660293579 26062087530223.22235488891...
result:
ok 100000 numbers
Test #13:
score: 0
Accepted
time: 409ms
memory: 158640kb
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.820000767708 242290432739284.395812988281 382427698314815.890747070312 16895448115472.124433517456 175161422.567836299917 75351167646370.300842285156 203278352090659.068893432617 119637497847007.953430175781 1480483568469.477017045021 126508943777914.200874328613 240306734905327.289779...
result:
ok 100000 numbers
Test #14:
score: 0
Accepted
time: 395ms
memory: 157272kb
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.000000000000 11677533560170374.119140625000 -1.000000000000 2327625177955291.306640625000 10593333095221014.542968750000 12710524468264700.602539062500 -1.000000000000 2019951545369944.578125000000 -1.000000000000 12445254039687679.818359375000 9559056375926235.102539062500 11419834997464112.9355...
result:
ok 100000 numbers
Test #15:
score: 0
Accepted
time: 394ms
memory: 155252kb
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:
15574462096016380.371093750000 10053475564194191.240234375000 15575656264873925.030273437500 15578451364341852.214843750000 15475194319450041.717773437500 15583907372907839.390625000000 14918882475507764.620117187500 15573693366188285.041015625000 15583166533434626.911132812500 15304002013976189.708...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 418ms
memory: 154060kb
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.649902343750 6444948610720401.959960937500 6906763735824260.351074218750 6698124103036643.305664062500 6404745518809350.555664062500 3935529254.335678219795 291733933253848.050720214844 6905207700103069.121582031250 6573585355062345.269042968750 1091222950371.523721635342 6710915828...
result:
ok 100000 numbers