QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#81907#2839. 3D GeometryAHSFNU_team_0#AC ✓162ms3684kbC++143.4kb2023-02-26 18:00:552023-02-26 18:03:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-26 18:03:35]
  • 评测
  • 测评结果:AC
  • 用时:162ms
  • 内存:3684kb
  • [2023-02-26 18:00:55]
  • 提交

answer

#include<bits/stdc++.h>
#define LL long long
#define LD long double
using namespace std;
LD X[5],Y[5],Z[5];
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0' || ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x=f? -x:x;return ;
}
inline LD calc(LD x,LD y,LD z)
{
	//printf(" calc %Lf %Lf %Lf\n",x,y,z);
	return x*y*z/6;
}
inline LD pw3(LD x)
{
	return x*x*x;
}
inline void print()
{
	//printf(" (%Lf,%Lf,%Lf) (%Lf,%Lf,%Lf) (%Lf,%Lf,%Lf) (%Lf,%Lf,%Lf)\n",X[1],Y[1],Z[1],X[2],Y[2],Z[2],X[3],Y[3],Z[3],X[4],Y[4],Z[4]);
}
int main()
{
	//freopen("data.out","r",stdin);
	//freopen("my.out","w",stdout);
	for(;~scanf("%Lf%Lf%Lf",&X[1],&Y[1],&Z[1]);)
	{
		for(int i=2;i<=4;++i)scanf("%Lf%Lf%Lf",&X[i],&Y[i],&Z[i]);
		if(X[2]<X[1])for(int i=1;i<=4;++i)X[i]=-X[i];
		if(Y[2]<Y[1])for(int i=1;i<=4;++i)Y[i]=-Y[i];
		if(Z[2]<Z[1])for(int i=1;i<=4;++i)Z[i]=-Z[i];
		if(X[3]>X[4])swap(X[3],X[4]);
		if(Y[3]>Y[4])swap(Y[3],Y[4]);
		if(Z[3]>Z[4])swap(Z[3],Z[4]);
		print();
		for(int i=4;i;--i)X[i]-=X[1],Y[i]-=Y[1],Z[i]-=Z[1];
		if(X[3]>=X[2] || Y[3]>=Y[2] || Z[3]>=Z[2])
		{
			puts("0");
			continue;
		}
		if(X[3]>X[1])
		{
			Y[2]*=(X[2]-X[3])/X[2];
			Z[2]*=(X[2]-X[3])/X[2];
			X[1]=X[3];
		}
		for(int i=4;i;--i)X[i]-=X[1],Y[i]-=Y[1],Z[i]-=Z[1];
		print();
		if(Y[3]>Y[1])
		{
			X[2]*=(Y[2]-Y[3])/Y[2];
			Z[2]*=(Y[2]-Y[3])/Y[2];
			Y[1]=Y[3];
		}
		for(int i=4;i;--i)X[i]-=X[1],Y[i]-=Y[1],Z[i]-=Z[1];
		print();
		if(Z[3]>Z[1])
		{
			X[2]*=(Z[2]-Z[3])/Z[2];
			Y[2]*=(Z[2]-Z[3])/Z[2];
			Z[1]=Z[3];
		}
		for(int i=4;i;--i)X[i]-=X[1],Y[i]-=Y[1],Z[i]-=Z[1];
		print();
		X[4]=min(X[4],X[2]);
		Y[4]=min(Y[4],Y[2]);
		Z[4]=min(Z[4],Z[2]);
		if(X[1]>=X[4] || Y[1]>=Y[4] || Z[1]>=Z[4])
		{
			puts("0");
			continue;
		}
		for(int i=4;i;--i)X[i]-=X[1],Y[i]-=Y[1],Z[i]-=Z[1];
		print();
		LD w=X[4]/X[2]+Y[4]/Y[2]+Z[4]/Z[2];
		LD tmp=0,res;
		if(w>=1)
		{
			//printf(" %Lf %Lf %Lf\n",pw3((X[2]-X[4])/X[2]),pw3((Y[2]-Y[4])/Y[2]),pw3((Z[2]-Z[4])/Z[2]));
			LD x0=(1-Y[4]/Y[2]-Z[4]/Z[2])*X[2],y0=(1-X[4]/X[2]-Z[4]/Z[2])*Y[2],z0=(1-X[4]/X[2]-Y[4]/Y[2])*Z[2],za,zb,zc;
			LD k=-Y[2]/X[2];
			//printf(" x0:%Lf y0:%Lf z0:%Lf\n",x0,y0,z0);
			res=calc(X[2],Y[2],Z[2]);
			tmp+=pw3((Z[2]-Z[4])/Z[2]);
			//printf(" +%Lf\n",(Z[2]-Z[4])/Z[2]);
			za=(1-X[4]/X[2])*Z[2];
			if(za>=Z[4])tmp-=pw3((za-Z[4])/Z[2]);
			//if(za>=Z[4])printf(" -%Lf\n",(za-Z[4])/Z[2]);
			zb=(1-Y[4]/Y[2])*Z[2];
			if(zb>=Z[4])tmp-=pw3((zb-Z[4])/Z[2]);
			//if(zb>=Z[4])printf(" -%Lf\n",(zb-Z[4])/Z[2]);
			tmp+=pw3((X[2]-X[4])/X[2]);
			//printf(" +%Lf\n",(X[2]-X[4])/X[2]);
			tmp+=pw3((Y[2]-Y[4])/Y[2]);
			//printf(" +%Lf\n",(Y[2]-Y[4])/Y[2]);
			//assert(fabs(((X[2]-(X[4]-Y[4]/k))/X[2])-((Y[2]-(Y[4]-k*X[4]))/Y[2]))<1e-9);
			//printf(" (%Lf)\n",X[4]-Y[4]/k);
			zc=max(X[2]-(X[4]-Y[4]/k),(LD)0)/X[2]*Z[2];
			tmp-=pw3(zc/Z[2]);
			//printf(" -%Lf\n",zc/Z[2]);
			//printf("tmp:%Lf\n",tmp);
			tmp=1-tmp;
			res*=tmp;
			//printf("res:%Lf\n",res);
			if(fabs(w-1)<=1e-9)assert(fabs(res-X[4]*Y[4]*Z[4])<=1e-9);
		}
		else res=X[4]*Y[4]*Z[4];
		printf("%.9Lf\n",res);
		/*if(fabs(w-1)<=1e-9)cerr<<(X[4]-X[1])*(Y[4]-Y[1])*(Z[4]-Z[1])-
			calc(X[4]-(1-Y[4]/Y[2]-Z[4]/Z[2])*X[2],
			Y[4]-(1-X[4]/X[2]-Z[4]/Z[2])*Y[2],
			Z[4]-(1-X[4]/X[2]-Y[4]/Y[2])*Z[2])
		<<" = "<<(X[4]-X[1])*(Y[4]-Y[1])*(Z[4]-Z[1])<<'\n';*/
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3500kb

input:

0 0 0
1 1 1
0 0 0
1 1 1
0 0 0
2 2 2
0 0 0
1 1 1
0 2 0
2 0 2
1 0 1
0 1 0

output:

0.166666667
0.833333333
0.166666667

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 137ms
memory: 3464kb

input:

-3 -4 2
-5 -5 4
0 0 3
3 4 2
1 5 2
-4 0 0
5 -5 0
-2 -1 3
5 4 2
3 -5 -1
0 -2 -1
-4 -4 -3
-4 4 -2
-2 2 -1
2 2 1
4 0 5
-4 1 0
-5 -2 4
-5 2 -4
5 0 1
2 5 1
-1 0 -3
-1 5 -4
-4 2 -2
2 2 -4
1 3 -1
2 4 2
-2 1 3
2 5 2
-2 -3 -5
-1 0 0
5 4 2
2 5 3
-3 -3 -3
5 4 -4
1 2 -3
2 -4 2
-3 -2 -2
2 -2 -1
-4 -5 3
4 -3 -3
-3...

output:

0
0
0
0
0.708333333
0
0
15.355654762
0
6.562500000
0
0
0
0
0
0
0
0
0
0
0
1.319444444
0
0.526748971
4.650000000
0
0
0
1.925925926
0
0
0
0
0
15.868888889
0.093750000
0
0
0
0
0
0
0
0
0
0
0.259259259
15.000000000
0.000755858
0
1.543209877
0
0
0.258503401
0
0
0
0
0
0
1.265625000
0
0.656597222
0
0
10.0000...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 153ms
memory: 3504kb

input:

-2 -2 -9
1 7 6
-3 -1 -4
-5 -6 2
-3 -4 -9
-10 -5 -4
0 2 -6
7 -9 2
6 4 5
-2 -6 0
8 -8 -3
-3 -10 2
10 -3 -8
-7 -5 -10
-9 -5 1
10 8 -1
7 9 10
6 3 9
-10 -10 -4
0 2 1
-2 4 9
10 5 -4
-6 6 3
7 4 8
6 5 2
3 -7 8
2 3 1
4 -10 7
-7 -3 -6
-10 5 -9
0 3 1
-5 -6 8
5 -3 8
-8 -8 -4
5 -10 4
0 3 1
9 -9 0
-8 8 -3
-7 9 -2...

output:

0
0
0
0
0
16.255732249
0.166666667
0
26.201923077
1.449891068
0
0
0
0
1.280276817
0
0
0
13.431240412
0
0
0
0.045454545
0
18.293333333
0
58.040816327
0
0
1.736111111
0
0
0
0
144.000000000
43.906250000
0
0.296712803
0
0
0
0
0
0
0
33.551038062
43.077942387
0.393750000
7.222222222
0
16.125000000
0
7.976...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 162ms
memory: 3464kb

input:

91 49 27
-66 89 -21
-22 35 78
-64 41 -19
93 87 -92
72 -32 -67
-48 28 -6
-50 20 78
-33 90 41
75 -51 43
89 9 -89
-35 -73 88
13 13 82
82 -40 72
-21 -75 36
15 79 -66
-21 -99 -49
-33 60 78
-27 -86 -64
61 66 96
-77 37 -71
72 -35 -9
38 86 -68
51 65 15
-16 -64 -25
-72 23 81
-20 60 60
-52 -99 19
24 83 27
-11...

output:

0
0
391.127206881
0
28313.212264151
0
11477.662564207
4368.006677006
14406.483590596
5814.427201071
0
50112.716889796
0
0
0
0
0
0
0
38.151407055
0
0
0
0
0
72.201948734
0
0
0
0
0
0
0
1923.686957716
0
0
3977.938348638
0
0
0
185.220000000
0
0
6771.861224386
0
0
0
2386.263855502
18857.288147055
0
182.04...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 156ms
memory: 3684kb

input:

-67 241 62
-271 -19 -199
364 487 343
293 433 -343
346 -321 78
-119 68 -487
-319 -45 -165
465 142 491
-310 476 -388
419 409 -124
167 -448 362
233 341 -119
9 -422 290
202 321 -217
310 216 286
172 10 -220
77 107 -282
352 -438 -26
171 81 111
-192 70 -132
376 -361 246
-371 354 -77
-400 -224 457
118 -387 ...

output:

0
417528.646965722
0
0
49064.274495413
5211742.513100331
3370766.246515174
0
0
84.405133541
165311.117708427
0
0
0
52736.152560963
0
132685.480972369
0
1436397.515315553
0
0
0
0
0
7356723.427007437
0
4878653.308295265
0
0
0
0
4575863.995235604
0
0
0
0
0
0
0
0
0
662108.378230373
0
0
0
0
0
13263.21337...

result:

ok 100000 numbers