QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369958 | #2827. Autobiography | PetroTarnavskyi# | WA | 0ms | 3720kb | C++20 | 4.6kb | 2024-03-28 20:06:56 | 2024-03-28 20:06:56 |
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 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, 2, 4)
{
FOR(j, 2, 4)
{
zs.PB((db)(-a * x[i] - b * y[j] - d) / c);
}
}
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 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;
};
const int MAGIC = 1e4;
db zMin = max(min(z[0], z[1]), z[2]), zMax = min(max(z[0], z[1]), z[3]);
db ans = 0;
FOR(i, 0, MAGIC)
{
db zet = zMin + (i + 0.5) / MAGIC * (zMax - zMin);
ans += f(zet);
}
cout << ans * (zMax - zMin) / MAGIC << "\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(4);
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: 0
Wrong Answer
time: 0ms
memory: 3720kb
input:
5 4 bbobo 1 3 2 3 3 4 4 5 4 6 bobo 1 2 1 3 1 4 2 3 2 4 3 4 4 0 bobo
output:
result:
wrong answer 1st lines differ - expected: '2', found: ''