QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#376318#4573. Global WarmingInfinityNSAC ✓424ms166528kbC++144.0kb2024-04-04 04:12:312024-04-04 04:12:33

Judging History

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

  • [2024-04-04 04:12:33]
  • 评测
  • 测评结果:AC
  • 用时:424ms
  • 内存:166528kb
  • [2024-04-04 04:12:31]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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