QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#308202 | #7783. Military Maneuver | mshcherba | RE | 0ms | 0kb | C++20 | 4.7kb | 2024-01-19 18:30:44 | 2024-01-19 18:30:44 |
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 {};
Pt p = inter(l, d.back().F);
if (SZ(d) < 2 || sgn(d.front().F.side(p)) >= 0)
{
if (!d.empty())
{
if (!parallel(l, d.front().F))
d.front().S = inter(l, d.front().F);
}
d.PB({l, p});
}
}
vector<Pt> res;
for (const 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: 0
Runtime Error
input:
0 0 2 2 2 3 1 1 3