QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#791251 | #2839. 3D Geometry | skip2004 | AC ✓ | 84ms | 4124kb | C++20 | 4.5kb | 2024-11-28 17:42:08 | 2024-11-28 17:42:08 |
Judging History
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);
}
}
详细
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