QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376276#4573. Global WarmingInfinityNSWA 12ms75864kbC++143.4kb2024-04-04 01:06:472024-04-04 01:06:47

Judging History

你现在查看的是最新测评结果

  • [2024-04-04 01:06:47]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:75864kb
  • [2024-04-04 01:06:47]
  • 提交

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'