QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#376316#4573. Global WarmingInfinityNSWA 313ms126488kbC++144.0kb2024-04-04 04:10:312024-04-04 04:10:32

Judging History

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

  • [2024-04-04 04:10:32]
  • 评测
  • 测评结果:WA
  • 用时:313ms
  • 内存:126488kb
  • [2024-04-04 04:10:31]
  • 提交

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);
	//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: 12ms
memory: 75588kb

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: 12ms
memory: 75596kb

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: 77612kb

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: 11ms
memory: 75632kb

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.670413754551
183.366793933067
33.490692646986
183.366793933067
183.366793933067

result:

ok 5 numbers

Test #5:

score: -100
Wrong Answer
time: 313ms
memory: 126488kb

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.679687500000
-1.000000000000
9067597268.201599121094
29490770935284.542968750000
21397921724094.820312500000
-1.000000000000
414425634047.640747070312
-1.000000000000
-1.000000000000
-1.000000000000
-1.000000000000
-1.000000000000
30771157933943.656250000000
-1.000000000000
2546840365...

result:

wrong answer 2502nd numbers differ - expected: '2.2145359', found: '2.2145386', error = '0.0000012'