QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308179 | #7783. Military Maneuver | mshcherba | TL | 0ms | 3792kb | C++20 | 4.7kb | 2024-01-19 18:13:11 | 2024-01-19 18:13:13 |
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 PI = acos(-1.0);
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);
}
ostream& operator<<(ostream& os, const Pt& p)
{
return os << "(" << p.x << "," << p.y << ")";
}
struct Line
{
Pt n;
db c;
Line (const Pt& _n, db _c): n(_n), c(_c) {}
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;
}
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 f(const vector<Pt>& v, db x0)
{
int n = SZ(v), iMin = 0, iMax = 0;
FOR(i, 0, SZ(v))
{
if (sgn(v[i].x - v[iMin].x) < 0)
iMin = i;
if (sgn(v[i].x - v[iMax].x) > 0)
iMax = i;
}
vector pwx(3, vector<db>(n));
FOR(i, 0, n)
{
pwx[0][i] = v[i].x * v[i].x;
pwx[1][i] = pwx[0][i] * v[i].x;
pwx[2][i] = pwx[1][i] * v[i].x;
}
db s0 = 0, s1 = 0, s2 = 0;
for (int s : {-1, 1})
{
for (int i = iMin; i != iMax;)
{
int j = i - s;
if (j < 0)
j += n;
if (j >= n)
j -= n;
db dx = v[j].x - v[i].x;
if (sgn(dx) != 0)
{
db k = (v[j].y - v[i].y) / dx;
db b = cross(v[j], v[i]) / dx;
db dx2 = (pwx[0][j] - pwx[0][i]) / 2;
db dx3 = (pwx[1][j] - pwx[1][i]) / 3;
db dx4 = (pwx[2][j] - pwx[2][i]) / 4;
s0 += s * (k * dx2 + b * dx);
s1 += s * (k * dx3 + b * dx2);
s2 += s * (k * dx4 + b * dx3);
}
i = j;
}
}
return s2 - 2 * x0 * s1 + x0 * x0 * s0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(15);
db xl, yl, xr, yr;
int n;
cin >> xl >> yl >> xr >> yr >> n;
vector<Pt> v(n);
for (Pt& p : v)
cin >> p.x >> p.y;
vector<Line> boundingLines =
{{{0, 1}, -yl}, {{-1, 0}, xr},
{{0, -1}, yr}, {{1, 0}, -xl}};
vector<Line> linesOuter, linesInner;
db ans = 0;
FOR(i, 0, n)
{
linesOuter = boundingLines;
linesInner = boundingLines;
FOR(j, 0, n)
{
if (j == i)
continue;
Pt normal = v[j] - v[i];
db c = -dot(normal, (v[i] + v[j]) / 2);
linesOuter.PB({normal, c});
linesInner.PB({normal * (-1), -c});
vector<Pt> vOuter = hplaneInter(linesOuter);
vector<Pt> vInner = hplaneInter(linesInner);
int s = 1;
for (auto polygon : {vOuter, vInner})
{
ans += s * f(polygon, v[i].x);
for (Pt& p : polygon)
swap(p.x, p.y);
reverse(ALL(polygon));
ans += s * f(polygon, v[i].y);
s *= -1;
}
}
}
cout << PI * ans / ((xr - xl) * (yr - yl)) << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
input:
0 0 2 2 2 3 1 1 3
output:
8.377580409572785
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
0 0 2 2 2 5 1 1 3
output:
37.699111843077503
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Time Limit Exceeded
input:
-2911 2151 336 5941 2000 -83 79 -94 47 48 -29 -47 64 84 75 -44 -86 -58 -11 -31 58 20 53 80 -19 -82 74 -60 -26 8 -68 -42 -61 -14 12 -58 -18 92 10 35 -26 71 64 76 89 -80 6 70 4 -96 -99 95 -80 -3 -22 71 -89 -75 17 -35 -82 -59 95 60 48 -74 50 -82 90 -26 5 -75 -31 -45 85 85 14 -70 -57 59 46 55 13 -23 60 ...