QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#56376#2839. 3D GeometryYaoBIG#AC ✓201ms3896kbC++2.4kb2022-10-19 01:14:372022-10-19 01:14:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-19 01:14:39]
  • 评测
  • 测评结果:AC
  • 用时:201ms
  • 内存:3896kb
  • [2022-10-19 01:14:37]
  • 提交

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;

template<class A> string to_string(A v) {
	string res = "{";
	int first = 1;
	for (const auto &x: v) {
		if (first == 0) res += ", ";
		res += to_string(x);
		first = 0;
	}
	res += "}";
	return res;
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(H h, T... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: "; debug_out(__VA_ARGS__)

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;


int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	using T = double;
	vector<T> xs(4), ys(4), zs(4);
	while (cin >> xs[0] >> ys[0] >> zs[0]) {
		rep(i, 1, 3) cin >> xs[i] >> ys[i] >> zs[i];
		if (xs[1] < xs[0]) {
			for (auto &x: xs) x *= -1;
		}
		if (ys[1] < ys[0]) {
			for (auto &x: ys) x *= -1;
		}
		if (zs[1] < zs[0]) {
			for (auto &x: zs) x *= -1;
		}
		T ox = xs[0], oy = ys[0], oz = zs[0];
		for (auto &x: xs) x -= ox;
		for (auto &x: ys) x -= oy;
		for (auto &x: zs) x -= oz;
		if (xs[2] > xs[3]) swap(xs[2], xs[3]);
		if (ys[2] > ys[3]) swap(ys[2], ys[3]);
		if (zs[2] > zs[3]) swap(zs[2], zs[3]);
		chmax(xs[2], xs[0]); chmin(xs[3], xs[1]);
		chmax(ys[2], ys[0]); chmin(ys[3], ys[1]);
		chmax(zs[2], zs[0]); chmin(zs[3], zs[1]);
		if (xs[2] > xs[3] || ys[2] > ys[3] || zs[2] > zs[3]) {
			puts("0");
		} else{
			T X = xs[1], Y = ys[1], Z = zs[1];
			T d = 1;
			T a = -d / X;
			T b = -d / Y;
			T c = -d / Z;
			
			auto cal = [&](T x, T y, T z) -> T {
				if (a * x + b * y + c * z + d <= 0) return 0;
				T res = 1.0;
				res *= (-d - b * y - c * z) / a - x;
				res *= (-d - a * x - c * z) / b - y;
				res *= (-d - a * x - b * y) / c - z;
				return res / 6.0;
			};
			T ans = 0;
			rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1) {
				T res = cal(xs[2 + i], ys[2 + j], zs[2 + k]);
				if ((i + j + k) & 1) ans -= res;
				else ans += res;
			}
			printf("%.10f\n", ans);
		}

	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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.1666666667
0.8333333333
0.1666666667

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 184ms
memory: 3808kb

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.7083333333
0.0000000000
0
15.3556547619
0.0000000000
6.5625000000
0
0
0
0.0000000000
0.0000000000
0.0000000000
0
0
0
0
0
1.3194444444
0
0.5267489712
4.6500000000
0
0
0.0000000000
1.9259259259
0
0
0
0.0000000000
0.0000000000
15.8688888889
0.0937500000
0
0.0000000000
0
0
0.0000000000
0
0.000...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 178ms
memory: 3692kb

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.2557322485
0.1666666667
0
26.2019230769
1.4498910675
0
0
0
0
1.2802768166
0
0
0
13.4312404120
0
0.0000000000
0
0.0454545455
0
18.2933333333
0
58.0408163265
0.0000000000
0
1.7361111111
0.0000000000
0
0
0
144.0000000000
43.9062500000
0.0000000000
0.2967128028
0
0
0
0
0.0000000000
0
0.0000...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 194ms
memory: 3852kb

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.1272068809
0
28313.2122641509
0
11477.6625642069
4368.0066770060
14406.4835905956
5814.4272010708
0
50112.7168897963
0
0
0
0
0
0.0000000000
0
38.1514070551
0
0
0
0
0
72.2019487337
0
0
0
0
0.0000000000
0
0
1923.6869577162
0
0
3977.9383486379
0
0
0.0000000000
185.2200000000
0
0
6771.8612243863...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 201ms
memory: 3896kb

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.6469657222
0
0.0000000000
49064.2744954128
5211742.5131003316
3370766.2465151735
0
0
84.4051335414
165311.1177084266
0
0.0000000000
0
52736.1525609631
0
132685.4809723693
0
1436397.5153155539
0
0
0
0
0
7356723.4270074358
0
4878653.3082952648
0
0
0
0
4575863.9952356052
0
0
0
0
0
0
0
0
0
6621...

result:

ok 100000 numbers