QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290096 | #7783. Military Maneuver | willow | WA | 1029ms | 4680kb | C++14 | 5.5kb | 2023-12-24 13:16:27 | 2023-12-24 13:16:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-9, pi = acos(-1);
int Dcmp(double x) {
return x < -eps ? -1 : x > eps ? 1 : 0;
}
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
Point operator + (Point rhs) {
return Point(x + rhs.x, y + rhs.y);
}
Point operator - (Point rhs) {
return Point(x - rhs.x, y - rhs.y);
}
double operator * (Point rhs) {
return x * rhs.x + y * rhs.y;
}
double operator ^ (Point rhs) {
return x * rhs.y - y * rhs.x;
}
Point operator * (double k) {
return Point(x * k, y * k);
}
Point operator / (double k) {
return Point(x / k, y / k);
}
Point Rotate90() {
return Point(y, -x);
}
double len2() {
return x * x + y * y;
}
double len() {
return sqrt(len2());
}
};
int Left(Point a, Point b, Point c) {
return Dcmp((b - a) ^ (c - a)) >= 0;
}
Point base;
vector<Point> Convex(vector<Point>a) {
int n = a.size(), cnt = 0;
if(n < 3)
return a;
base = a[0];
for(auto p : a)
if(make_pair(p.x, p.y) < make_pair(base.x, base.y))
base = p;
sort(a.begin(), a.end(), [](Point a, Point b) {
int d = Dcmp((a - base) ^ (b - base));
if(d)
return d > 0;
return (a - base).len() < (b - base).len();
});
vector<Point>res;
for(int i = 0; i < n; ++ i) {
while(cnt > 1 && Left(res[cnt - 2], a[i], res[cnt - 1]))
-- cnt, res.pop_back();
res.push_back(a[i]), ++ cnt;
}
return res;
}
struct Line {
Point s, t;
Line(Point s = Point(), Point t = Point()) : s(s), t(t) {}
};
bool OnLeft(Line l, Point p) {
return Left(l.s, l.t, p);
}
Point LineInter(Line l1, Line l2) {
// cerr << "Inter: " << endl;
// cerr << "(" << l1.s.x << ", " << l1.s.y << ") -- (" << l1.t.x << ", " << l1.t.y << ")" << endl;
// cerr << "(" << l2.s.x << ", " << l2.s.y << ") -- (" << l2.t.x << ", " << l2.t.y << ")" << endl;
double a1 = (l2.t - l2.s) ^ (l1.s - l2.s), a2 = (l2.t - l2.s) ^ (l1.t - l2.s);
return (l1.s * a2 - l1.t * a1) / (a2 - a1);
}
Line Middle(Point s, Point t) {
Point p = (s + t) / 2, v = (t - s).Rotate90();
assert(Left(p, p - v, s));
return Line(p, p - v);
}
vector<Point> Intersect(vector<Line> h) {
typedef pair<double, Line> polar;
vector<polar> g;
for(auto l : h) {
Point v = l.t - l.s;
g.push_back(make_pair(atan2(v.y, v.x), l));
}
sort(g.begin(), g.end(), [] (polar a, polar b) {
if(Dcmp(a.first - b.first) == 0)
return Dcmp((a.second.t - a.second.s) ^ (b.second.t - b.second.s)) < 0;
return Dcmp(a.first - b.first) < 0;
});
h.resize(unique(g.begin(), g.end(), [] (polar a, polar b) {
return Dcmp(a.first - b.first) == 0;
}) - g.begin());
for(int i = 0; i < (int)h.size(); ++ i)
h[i] = g[i].second;
int fore = 0, rear = -1;
vector<Line> ret;
ret.clear();
for(int i = 0; i < (int)h.size(); ++ i) {
while(fore < rear && !OnLeft(h[i], LineInter(ret[rear - 1], ret[rear])))
-- rear, ret.pop_back();
while(fore < rear && !OnLeft(h[i], LineInter(ret[fore], ret[fore + 1])))
++ fore;
++ rear, ret.push_back(h[i]);
}
while(rear - fore > 1 && !OnLeft(ret[fore], LineInter(ret[rear - 1], ret[rear])))
-- rear, ret.pop_back();
while(rear - fore > 1 && !OnLeft(ret[rear], LineInter(ret[fore], ret[fore + 1])))
++ fore;
if(rear - fore < 2)
return vector<Point>();
vector<Point> ans;
ans.resize(rear - fore + 1);
for(int i = 0; i < (int)ans.size(); ++ i)
ans[i] = LineInter(ret[fore + i], ret[fore + (i + 1) % ans.size()]);
return ans;
}
const int maxn = 2005, inf = 2e4;
int xl, yl, xr, yr, n;
Point p[maxn];
double ans;
void Calc(vector<Point> poly, Point p, int coef) {
int n = (int)poly.size();
double area = 0;
for(int i = 0; i < n; ++ i) {
area += poly[i] ^ poly[(i + 1) % n];
}
area /= 2;
ans += area * p.len2() * coef;
double sx = 0, sy = 0;
for(int i = 0; i < n; ++ i) {
Point p1 = poly[i], p2 = poly[(i + 1) % n];
sx += (p1.x + p2.x) * (p1 ^ p2);
sy += (p1.y + p2.y) * (p1 ^ p2);
}
sx /= 6, sy /= 6;
ans -= sx * (2 * p.x) * coef;
ans -= sy * (2 * p.y) * coef;
}
int main() {
scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
scanf("%d", &n);
for(int i = 1, x, y; i <= n; ++ i) {
scanf("%d%d", &x, &y);
p[i] = Point(x, y);
}
for(int i = 1; i <= n; ++ i) {
vector<Line> vl;
vl.clear();
vl.push_back(Line(Point(xl, inf), Point(xl, -inf)));
vl.push_back(Line(Point(-inf, yl), Point(inf, yl)));
vl.push_back(Line(Point(xr, -inf), Point(xr, inf)));
vl.push_back(Line(Point(inf, yr), Point(-inf, yr)));
for(int j = 1; j <= n; ++ j) {
if(i != j) {
vl.push_back(Middle(p[j], p[i]));
}
}
auto vp = Convex(Intersect(vl));
if(!vp.size())
continue;
// cerr << "Point(" << p[i].x << ", " << p[i].y << "): ";
// for(auto p : vp)
// cerr << p.x << " " << p.y << endl;
// cerr << endl;
Calc(vp, p[i], 1);
}
// cerr << ans << endl;
for(int i = 1; i <= n; ++ i) {
vector<Line> vl;
vl.clear();
vl.push_back(Line(Point(xl, inf), Point(xl, -inf)));
vl.push_back(Line(Point(-inf, yl), Point(inf, yl)));
vl.push_back(Line(Point(xr, -inf), Point(xr, inf)));
vl.push_back(Line(Point(inf, yr), Point(-inf, yr)));
for(int j = 1; j <= n; ++ j) {
if(i != j) {
vl.push_back(Middle(p[i], p[j]));
}
}
auto vp = Convex(Intersect(vl));
if(!vp.size())
continue;
// cerr << "Point(" << p[i].x << ", " << p[i].y << "): ";
// for(auto p : vp)
// cerr << p.x << " " << p.y << endl;
// cerr << endl;
Calc(vp, p[i], -1);
}
// cerr << ans << endl;
ans /= (xr - xl) * (yr - yl);
printf("%.15f\n", ans * pi);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4188kb
input:
0 0 2 2 2 3 1 1 3
output:
8.377580409572779
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4180kb
input:
0 0 2 2 2 5 1 1 3
output:
37.699111843077517
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 1029ms
memory: 4680kb
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 ...
output:
11260841.620147660374641
result:
wrong answer 1st numbers differ - expected: '6657168.1428534', found: '11260841.6201477', error = '0.6915363'