QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#376276 | #4573. Global Warming | InfinityNS | WA | 12ms | 75864kb | C++14 | 3.4kb | 2024-04-04 01:06:47 | 2024-04-04 01:06:47 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ldb 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);
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;
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;
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);
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;
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]);
AddTriangle(i,A,B,M);
AddTriangle(i,B,M,C);
}else{
AddTriangle(i,A,B,C);
}
AddFormula(i,mnz,area,0,0);
}
}
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]){
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 75724kb
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: -100
Wrong Answer
time: 11ms
memory: 75864kb
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:
115.632563988734 -1.000000000000 83.226418131085 57.478442572137 34.920830870645 15.621732301976 -1.000000000000
result:
wrong answer 1st numbers differ - expected: '120.4834054', found: '115.6325640', error = '0.0402615'