QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791251#2839. 3D Geometryskip2004AC ✓84ms4124kbC++204.5kb2024-11-28 17:42:082024-11-28 17:42:08

Judging History

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

  • [2024-11-28 17:42:08]
  • 评测
  • 测评结果:AC
  • 用时:84ms
  • 内存:4124kb
  • [2024-11-28 17:42:08]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
const int N = 200005;
const db eps = 1e-8;
db sgn(db x) {
	return x < -eps ? -1 : x > eps;
}
struct p3 {
	db x, y, z;
	db norm() {
		return x * x + y * y + z * z;
	}
};
p3 operator + (p3 x, p3 y) { return {x.x + y.x, x.y + y.y, x.z + y.z}; }
p3 operator - (p3 x, p3 y) { return {x.x - y.x, x.y - y.y, x.z - y.z}; }
p3 operator * (p3 x, db y) { return {x.x * y, x.y * y, x.z * y}; }
p3 operator / (p3 x, db y) { return {x.x / y, x.y / y, x.z / y}; }
db operator % (p3 x, p3 y) { return x.x * y.x + x.y * y.y + x.z * y.z; }
p3 operator * (p3 x, p3 y) {
	return {x.y * y.z - x.z * y.y,
		x.z * y.x - x.x * y.z,
		x.x * y.y - x.y * y.x};
}
struct plane {
	p3 n; db d;
	plane(p3 v, db d) : n(v), d(d) {}
	db side(p3 x) const { return n % x + d; }
	plane(p3 a, p3 b, p3 c) : n((c - a) * (b - a)) {
		d = -(n % a);
	}
};
struct line3 {
	p3 d, o;
	line3(plane p1, plane p2) : d(p1.n * p2.n) {
		o = (p2.n * p1.d - p1.n * p2.d) * (-1.) * d / d.norm();
	}
	p3 operator & (const plane & p) const {
		return o - d * p.side(o) / (p.n % d);
	}
};
struct p2 {
	db x, y;
	db abs() const {
		return sqrt(x * x + y * y);
	}
};
p2 r90(p2 x) {
	return {-x.y, x.x};
}
p2 operator + (p2 x, p2 y) { return {x.x + y.x, x.y + y.y}; }
p2 operator - (p2 x, p2 y) { return {x.x - y.x, x.y - y.y}; }
p2 operator / (p2 x, db y) { return {x.x / y, x.y / y}; }
db operator * (p2 x, p2 y) { return x.x * y.y - x.y * y.x; }
struct line  : p2 {
	db z;
	line() {}
	line(p2 a, p2 b) : p2(r90(b - a)), z(a * b) {

	}
	db operator () (p2 a) const {
		return a.x * x + a.y * y + z;
	}
	void red() {
		db v = abs();
		x /= v;
		y /= v;
		z /= v;
	}
};
p2 operator & (line x, line y) {
	return p2{p2{x.z, x.y} * p2{y.z, y.y}, p2{x.x, x.z} * p2{y.x, y.z}} / -(p2(x) * p2(y));
}
std::vector<p2> cut(std::vector<p2> & o, line l) {
	static std::vector<p2> res;
	res.clear();
	int n = size(o);
	l.red();
	for(int i = 0;i < n;++i) {
		p2 a = o[i], b = o[i == n - 1 ? 0 : i + 1];
		int va = sgn(l(a));
		int vb = sgn(l(b));
		if(va >= 0) res.push_back(a);
		if(va * vb < 0) res.push_back(line(a, b) & l);
	}
	if(res.size() <= 2) return {};
	return res;
}
std::vector<plane> ps;
std::vector<line> ls;
void init() {
	ls.resize(ps.size());
	for(int i = 0;i < (int) ps.size();++i) {
		ls[i].x = ps[i].n.x;
		ls[i].y = ps[i].n.y;
		ls[i].z = ps[i].d;
	}
}

db area(db z) {
	std::vector<p2> v = {
		p2{-500, -500},
		p2{500, -500},
		p2{500, 500},
		p2{-500, 500}
	};
	for(int i = 0;i < (int) ps.size();++i) {
		line tmp = ls[i];
		tmp.z += ps[i].n.z * z;
		if(tmp.abs() > eps) {
			v = cut(v, tmp); } else {
			if(tmp.z < -eps) {
				return 0;
			}
		}
		if(v.empty()) return 0;
	}
	db sum = 0;
	for(int i = 2;i < (int) v.size();++i) {
		sum += (v[i - 1] - v[0]) * (v[i] - v[0]);
	}
	return sum;
}


db g(db a, db b, db c) {
	return (a + b * 4 + c) / 6;
}
db simp(db l, db m, db r, db vl, db vm, db vr) {
	db ml = (l + m) / 2, vml = area(ml);
	db mr = (r + m) / 2, vmr = area(mr);
	if(fabs(g(vl, vml, vm) + g(vm, vmr, vr) - g(vl, vm, vr) * 2) * (r - l) < 1e-6) {
		return (g(vl, vml, vm) + g(vm, vmr, vr)) / 2 * (r - l);
	}
	return simp(l, ml, m, vl, vml, vm) + simp(m, mr, r, vm, vmr, vr);
}
int main() {
#ifdef zqj
	//freopen("1.in", "r", stdin);
#endif
	std::ios::sync_with_stdio(false), cin.tie(0);
	int x[5], y[5], z[5];
	for(;cin >> x[1] >> y[1] >> z[1];) {
		for(int j = 2;j <= 4;++j) {
			cin >> x[j] >> y[j] >> z[j];
		}
		for(int * a : {x, y, z}) if(a[2] < a[1])
			for(int j = 1;j <= 4;++j) {
				a[j] *= -1;
			}
		p3 D {x[1], y[1], z[1]};
		p3 A {x[2], y[1], z[1]};
		p3 B {x[1], y[2], z[1]};
		p3 C {x[1], y[1], z[2]};
		if(x[3] > x[4]) std::swap(x[3], x[4]);
		if(y[3] > y[4]) std::swap(y[3], y[4]);
		if(z[3] > z[4]) std::swap(z[3], z[4]);
		auto volume = [&](p3 d, p3 a, p3 b, p3 c) {
			return (d - a) % ((b - a) * (c - a));
		};
		if(volume(D, A, B, C) < 0) {
			std::swap(A, C);
		}

		plane P(A, B, C);
		db sum = 0;
		db sideD = -P.side(D);
		for(int j = 0;j < 8;++j) {
			int u = x[1], v = y[1], w = z[1];
			u = std::max(u, x[3 + (j >> 0 & 1)]);
			v = std::max(v, y[3 + (j >> 1 & 1)]);
			w = std::max(w, z[3 + (j >> 2 & 1)]);
			p3 p{u,v,w};
			db sidep = -P.side(p);
			if(sidep >= 0) {
				db S = sidep / sideD;
				S *= S * S;
				sum += (__builtin_popcount(j) % 2 ? -1 : 1) * S;
			}
		}
		printf("%.10lf\n", sum * volume(D, A, B, C) / 6);

	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3756kb

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: 74ms
memory: 4124kb

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.0000000000
0.0000000000
0.0000000000
0.0000000000
0.7083333333
0.0000000000
0.0000000000
15.3556547619
0.0000000000
6.5625000000
0.0000000000
0.0000000000
-0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
1.3194444444
0.0000000000...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 76ms
memory: 3976kb

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.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
16.2557322485
0.1666666667
0.0000000000
26.2019230769
1.4498910675
0.0000000000
0.0000000000
0.0000000000
0.0000000000
1.2802768166
0.0000000000
0.0000000000
0.0000000000
13.4312404120
0.0000000000
0.0000000000
0.0000000000
0.045454545...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 80ms
memory: 3912kb

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.0000000000
0.0000000000
391.1272068809
0.0000000000
28313.2122641509
0.0000000000
11477.6625642069
4368.0066770060
14406.4835905956
5814.4272010708
0.0000000000
50112.7168897963
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
38.1514070551
0.0000000000
0....

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 84ms
memory: 4104kb

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.0000000000
417528.6469657218
0.0000000000
0.0000000000
49064.2744954128
5211742.5131003335
3370766.2465151721
0.0000000000
0.0000000000
84.4051335414
165311.1177084265
0.0000000000
0.0000000000
0.0000000000
52736.1525609632
0.0000000000
132685.4809723694
0.0000000000
1436397.5153155532
0.000000000...

result:

ok 100000 numbers