QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#64253#2839. 3D GeometrylyhyAC ✓149ms3680kbC++142.5kb2022-11-24 14:20:442022-11-24 14:21:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-24 14:21:09]
  • 评测
  • 测评结果:AC
  • 用时:149ms
  • 内存:3680kb
  • [2022-11-24 14:20:44]
  • 提交

answer

#include<iostream>
#include<math.h>
#include<bits/stdc++.h>

using namespace std;

int x[5], y[5], z[5];
double aa, bb, cc, all;

int get(int l, int r){
	return rand() % (r - l + 1) + l;
}

double ask(int x0, int y0, int z0){
	
	double ret;
	
	x[1] -= x0; x[2] -= x0;
	y[1] -= y0; y[2] -= y0;
	z[1] -= z0; z[2] -= z0;
//	cout << "begin\n";
//	cout << x[1] << " " << y[1] << " " << z[1] << endl;
//	cout << x[2] << " " << y[2] << " " << z[2] << endl;
	
	int x1 = x[2], y1 = y[1], z1 = z[1];
	int x2 = x[1], y2 = y[2], z2 = z[1];
	int x3 = x[1], y3 = y[1], z3 = z[2];
	int a = (y2 - y1) * (z3 - z1) - (y3 - y1) * (z2 - z1);
	int b = (z2 - z1) * (x3 - x1) - (z3 - z1) * (x2 - x1);
	int c = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
	int d = - a * x1 - b * y1 - c * z1;

	double xx = 1.0 * (-d) / a;	
	double yy = 1.0 * (-d) / b;
	double zz = 1.0 * (-d) / c;
	
	
//	cout << xx << "  " << yy << "  " << zz << endl;
	xx = min(xx, (double)x[2]) - max(0, x[1]);
	yy = min(yy, (double)y[2]) - max(0, y[1]);
	zz = min(zz, (double)z[2]) - max(0, z[1]);

	double k = min({xx / aa, yy / bb, zz / cc});
	if(k < 0) ret = 0;
	else ret = all * k * k * k;
//		ret = xx * yy * zz / 6;
//	cout << " xyz : " << xx << "  " << yy << "  " << zz << endl;
	
	x[1] += x0; x[2] += x0;
	y[1] += y0; y[2] += y0;
	z[1] += z0; z[2] += z0;	
	
//	cout << x0 << " " << y0 << " " << z0 << "       " << ret <<  "   ";

	return ret;
}

int main(){
	
	std::ios::sync_with_stdio(false);
	
	srand(time(0));
	
	while(cin >> x[1] >> y[1] >> z[1]){
		for(int i = 2; i <= 4; i ++){
			cin >> x[i] >> y[i] >> z[i];
			x[i] -= x[1];
			y[i] -= y[1];
			z[i] -= z[1];
		}
		x[1] = y[1] = z[1] = 0;
		
		if(x[2] < 0)
			for(int i = 1; i <= 4; i ++)
				x[i] = -x[i];
			
		if(y[2] < 0)
			for(int i = 1; i <= 4; i ++)
				y[i] = -y[i];
	
		if(z[2] < 0)
			for(int i = 1; i <= 4; i ++)
				z[i] = -z[i];
				
		aa = x[2];
		bb = y[2];
		cc = z[2];
		all = aa * bb * cc / 6.0;
		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]);
			
//		cout << endl;
//		for(int i = 1; i <= 4; i ++)
//			cout << x[i] << " " << y[i] << " " << z[i] << endl;
				
//		ask(-1, -1, -1);
				
		double ans = ask(x[3], y[3], z[3]) 
			- ask(x[4], y[3], z[3]) - ask(x[3], y[4], z[3]) - ask(x[3], y[3], z[4])
			+ ask(x[3], y[4], z[4]) + ask(x[4], y[3], z[4]) + ask(x[4], y[4], z[3])
			- ask(x[4], y[4], z[4]);
		
		printf("%.8lf\n", fabs(ans));
	}
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.16666667
0.83333333
0.16666667

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 110ms
memory: 3592kb

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.00000000
0.00000000
0.00000000
0.00000000
0.70833333
0.00000000
0.00000000
15.35565476
0.00000000
6.56250000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
1.31944444
0.00000000
0.52674897
4.65000000
0.00000000
0.00000000
0....

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 118ms
memory: 3596kb

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.00000000
0.00000000
0.00000000
0.00000000
0.00000000
16.25573225
0.16666667
0.00000000
26.20192308
1.44989107
0.00000000
0.00000000
0.00000000
0.00000000
1.28027682
0.00000000
0.00000000
0.00000000
13.43124041
0.00000000
0.00000000
0.00000000
0.04545455
0.00000000
18.29333333
0.00000000
58.0408163...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 120ms
memory: 3664kb

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.00000000
0.00000000
391.12720688
0.00000000
28313.21226415
0.00000000
11477.66256421
4368.00667701
14406.48359060
5814.42720107
0.00000000
50112.71688980
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
38.15140706
0.00000000
0.00000000
0.00000000
0.00000000
0.00000000
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 149ms
memory: 3548kb

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.00000000
417528.64696572
0.00000000
0.00000000
49064.27449541
5211742.51310033
3370766.24651517
0.00000000
0.00000000
84.40513354
165311.11770843
0.00000000
0.00000000
0.00000000
52736.15256096
0.00000000
132685.48097237
0.00000000
1436397.51531555
0.00000000
0.00000000
0.00000000
0.00000000
0.000...

result:

ok 100000 numbers