QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#370083 | #2839. 3D Geometry | PetroTarnavskyi | AC ✓ | 796ms | 3984kb | C++20 | 5.2kb | 2024-03-28 21:45:37 | 2024-03-28 21:45:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef long double db;
const db EPS = 1e-9;
struct Pt
{
db x, y;
Pt operator+(const Pt& p) const
{
return {x + p.x, y + p.y};
}
Pt operator-(const Pt& p) const
{
return {x - p.x, y - p.y};
}
Pt operator*(db d) const
{
return {x * d, y * d};
}
Pt operator/(db d) const
{
return {x / d, y / d};
}
};
db sq(const Pt& p)
{
return p.x * p.x + p.y * p.y;
}
db abs(const Pt& p)
{
return sqrt(sq(p));
}
int sgn(db x)
{
return (EPS < x) - (x < -EPS);
}
Pt perp(const Pt& p)
{
return {-p.y, p.x};
}
db dot(const Pt& p, const Pt& q)
{
return p.x * q.x + p.y * q.y;
}
db cross(const Pt& p, const Pt& q)
{
return p.x * q.y - p.y * q.x;
}
bool half(const Pt& p)
{
assert(sgn(p.x) != 0 || sgn(p.y) != 0);
return sgn(p.y) == -1 ||
(sgn(p.y) == 0 && sgn(p.x) == -1);
}
struct Line
{
Pt n;
db c;
Line(const Pt& p, const Pt& q):
n(perp(q - p)), c(-dot(n, p)) {}
db side(const Pt& p) const
{
return dot(n, p) + c;
}
};
bool parallel(const Line& l1, const Line& l2)
{
return sgn(cross(l1.n, l2.n)) == 0;
}
Pt inter(const Line& l1, const Line& l2)
{
db d = cross(l1.n, l2.n);
assert(sgn(d) != 0);
return perp(l2.n * l1.c - l1.n * l2.c) / d;
}
db areaPolygon(const vector<Pt>& v)
{
db area = 0.0;
int n = SZ(v);
FOR(i, 0, n)
area += cross(v[i], v[(i + 1) % n]);
return abs(area) / 2.0;
}
vector<Pt> hplaneInter(vector<Line> lines)
{
sort(ALL(lines), [](const Line& l1, const Line& l2)
{
bool h1 = half(l1.n), h2 = half(l2.n);
if (h1 != h2)
return h1 < h2;
int p = sgn(cross(l1.n, l2.n));
if (p != 0)
return p > 0;
return sgn(l1.c / abs(l1.n) - l2.c / abs(l2.n)) < 0;
});
lines.erase(unique(ALL(lines), parallel), lines.end());
deque<pair<Line, Pt>> d;
for (const Line& l : lines)
{
while (SZ(d) > 1 && sgn(l.side((d.end() - 1)->S)) < 0)
d.pop_back();
while (SZ(d) > 1 && sgn(l.side((d.begin() + 1)->S)) < 0)
d.pop_front();
if (!d.empty() && sgn(cross(d.back().F.n, l.n)) <= 0)
return {};
if (SZ(d) < 2 || sgn(d.front().F.side(inter(l, d.back().F))) >= 0)
{
Pt p;
if (!d.empty())
{
p = inter(l, d.back().F);
if (!parallel(l, d.front().F))
d.front().S = inter(l, d.front().F);
}
d.PB({l, p});
}
}
vector<Pt> res;
for (auto [l, p] : d)
{
if (res.empty() || sgn(sq(p - res.back())) > 0)
res.PB(p);
}
return res;
}
db x[4], y[4], z[4];
tuple<db, db, db> cross(db x1, db y1, db z1, db x2, db y2, db z2)
{
return {y1 * z2 - z1 * y2, z1 * x2 - x1 * z2, x1 * y2 - y1 * x2};
}
void solve()
{
FOR(i, 1, 4)
cin >> x[i] >> y[i] >> z[i];
vector<db> zs = {(db)z[0], (db)z[1], (db)z[2], (db)z[3]};
auto [a, b, c] = cross(x[0] - x[1], y[1] - y[0], 0, x[0] - x[1], 0, z[1] - z[0]);
db d = -a * x[1] - b * y[0] - c * z[0];
//cerr << "d = " << d << endl;
if (x[2] > x[3])
swap(x[2], x[3]);
if (y[2] > y[3])
swap(y[2], y[3]);
if (z[2] > z[3])
swap(z[2], z[3]);
FOR(i, 0, 4)
{
FOR(j, 0, 4)
{
zs.PB(((db)-a * x[i] - b * y[j] - d) / c);
// cerr << zs.back() << "\n";
}
}
sort(ALL(zs));
vector<Line> lines;
lines.PB({{x[2], y[2]}, {x[3], y[2]}});
lines.PB({{x[3], y[2]}, {x[3], y[3]}});
lines.PB({{x[3], y[3]}, {x[2], y[3]}});
lines.PB({{x[2], y[3]}, {x[2], y[2]}});
Pt p = {x[0], y[0]}, q = {x[1], y[0]}, r = {x[0], y[1]};
FOR(it, 0, 2)
{
if (sgn(cross(q - p, r - p)) > 0)
lines.PB({p, q});
else
lines.PB({q, p});
swap(q, r);
}
auto f = [&](db zet)
{
db alpha = (zet - z[1]) / (z[0] - z[1]);
if (sgn(alpha) == 0)
{
return db(0.0);
}
Pt qAlpha = p + (q - p) * alpha;
Pt rAlpha = p + (r - p) * alpha;
if (sgn(cross(q - p, r - p)) > 0)
lines.PB({qAlpha, rAlpha});
else
lines.PB({rAlpha, qAlpha});
db res = areaPolygon(hplaneInter(lines));
lines.pop_back();
return res;
};
/*for (auto zet : zs)
cerr << zet << " ";
cerr << endl;*/
db ans = 0;
FOR(i, 0, SZ(zs) - 1)
{
db z1 = zs[i], z2 = (zs[i] + zs[i + 1]) / 2.0, z3 = zs[i + 1];
if ((z2 < min(z[0], z[1]) || z2 > max(z[0], z[1]) || z2 < min(z[2], z[3]) || z2 > max(z[2], z[3])))
continue;
//cerr << i << '\n';
//cerr << z1 << " " << z2 << " " << z3 << endl;
//cerr << "z1 " << z1 << " " << f(z1) << endl;
//cerr << "z2 " << z2 << " " << f(z2) << endl;
//cerr << "z3 " << z3 << " " << f(z3) << endl;
ans += (z3 - z1) * (f(z1) + 4 * f(z2) + f(z3));
}
//if (abs(ans - 7.500000) < 1e-3)
//{
// cout << setprecision(1);
// FOR (i, 0, 4)
// {
// cout << x[i] << '#' << y[i] << '#' << z[i] << '$';
// }
// return;
//}
cout << ans / 6 << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
while (cin >> x[0] >> y[0] >> z[0])
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3984kb
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.166666666666667 0.833333333333333 0.166666666666667
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 796ms
memory: 3848kb
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.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.708333333333333 0.000000000000000 0.000000000000000 15.355654761904762 0.000000000000000 6.562500000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 720ms
memory: 3952kb
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.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 16.255732248520710 0.166666666666667 0.000000000000000 26.201923076923077 1.449891067538126 0.000000000000000 0.000000000000000 0.000000000000000 0.000000000000000 1.280276816608997 0.000000000000000 0.00000000...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 689ms
memory: 3952kb
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.000000000000000 0.000000000000000 391.127206880941601 0.000000000000000 28313.212264150943398 0.000000000000000 11477.662564206886030 4368.006677005977706 14406.483590595559708 5814.427201070791197 0.000000000000000 50112.716889796352838 0.000000000000000 0.000000000000000 0.000000000000000 0.0000...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 674ms
memory: 3928kb
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.000000000000000 417528.646965721876086 0.000000000000000 0.000000000000000 49064.274495412844026 5211742.513100331297665 3370766.246515173515490 0.000000000000000 0.000000000000000 84.405133541449877 165311.117708426522356 0.000000000000000 0.000000000000000 0.000000000000000 52736.152560963166984...
result:
ok 100000 numbers