QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344527 | #7783. Military Maneuver | ucup-team1209 | WA | 43ms | 3992kb | C++20 | 2.7kb | 2024-03-04 18:35:52 | 2024-03-04 18:35:52 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin, std::cout;
using ll = long long;
using u64 = unsigned long long;
using db = double;
using f64 = long double;
struct vec2 {
db x, y;
db norm() const { return x * x + y * y; }
db abs() const { return std::sqrt(norm()); }
};
const db eps = 1e-8;
db sgn(db x) {
return x < -eps ? -1 : x > eps;
}
vec2 operator + (vec2 x, vec2 y) { return {x.x + y.x, x.y + y.y}; }
vec2 operator - (vec2 x, vec2 y) { return {x.x - y.x, x.y - y.y}; }
vec2 operator / (vec2 x, db y) { return {x.x / y, x.y / y}; }
f64 operator * (vec2 x, vec2 y) { return x.x * y.y - x.y * y.x; }
vec2 r90(vec2 x) {
return {-x.y, x.x};
}
struct line : vec2 {
db z;
line(db a, db b, db c) : vec2({a, b}), z(c) {}
line(vec2 a, vec2 b) : vec2(r90(b - a)), z(a * b) {}
db operator () (vec2 o) const { return o.x * x + o.y * y + z; }
line perp() const { return {y, -x, 0}; }
line para(vec2 o) { return {x, y, z - (*this)(o) }; }
db abs() const { return sqrt(x * x + y * y); }
db side(vec2 x) const {
return sgn((*this)(x) / abs());
}
};
vec2 operator & (line x, line y) {
return vec2{vec2{x.z, x.y} * vec2{y.z, y.y}, vec2{x.x, x.z} * vec2{y.x, y.z}} / -(vec2(x) * vec2(y));
}
line bisector(vec2 a, vec2 b) {
return line(b, a).perp().para((a + b) / 2);
}
f64 det(line a, line b, line c) {
vec2 A = a, B = b, C = c;
return c.z * (A * B) + a.z * (B * C) + b.z * (C * A);
}
db check(line a, line b, line c) {
return sgn(det(a, b, c)) * sgn(vec2(a) * vec2(b));
}
std::vector<vec2> cut(const std::vector<vec2> & o, line l) {
std::vector<vec2> res;
int n = size(o);
for(int i = 0;i < n;++i) {
vec2 a = o[i], b = o[(i + 1) % n];
if(l.side(a) >= 0) res.push_back(a);
if(l.side(a) * l.side(b) < 0) res.push_back(line(a, b) & l);
}
return res;
}
db calc(std::vector<vec2> v, vec2 p) {
db sum = 0;
for(int i = 0;i < (int) v.size();++i) {
vec2 a = v[i] - p, b = v[(i + 1) % v.size()] - p;
sum += a * b * (a.norm() / 3 + b.norm() / 3 + (a * b) / 6);
}
return sum;
}
db calc(std::vector<vec2> p, std::vector<vec2> init) {
std::mt19937 gen(114514);
shuffle(p.begin(), p.end(), gen);
db ans = 0;
for(int i = 0;i < (int) p.size();++i) {
auto A = init, B = init;
for(vec2 x : p) if((x - p[i]).abs() > eps) {
A = cut(A, bisector(p[i], x));
B = cut(B, bisector(x, p[i]));
}
ans += calc(B, p[i]);
ans -= calc(A, p[i]);
}
return ans;
}
db xl, yl, xr, yr;
int main() {
cin >> xl >> yl >> xr >> yr;
int n; cin >> n;
std::vector<vec2> a(n);
for(auto & [x, y] : a) cin >> x >> y;
db res = calc(a, { {xl, yl}, {xr, yl}, {xr, yr}, {xl, yr} });
printf("%.10lf\n", res / (xr - xl) / (yr - yl) * std::acos(-1) / 3);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3992kb
input:
0 0 2 2 2 3 1 1 3
output:
8.3775804096
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
0 0 2 2 2 5 1 1 3
output:
37.6991118431
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: -100
Wrong Answer
time: 43ms
memory: 3904kb
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:
6794254.7831411967
result:
wrong answer 1st numbers differ - expected: '6657168.1428534', found: '6794254.7831412', error = '0.0205923'