QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#402612 | #7783. Military Maneuver | Jose_17 | WA | 2288ms | 4340kb | C++20 | 6.6kb | 2024-05-01 01:49:55 | 2024-05-01 01:49:55 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()
const int Inf = 1e9;
const ll INF = 1e18;
const int maxn = 1e5;
using ld = long double;
const ld eps = 1e-9, inf = 1e8, pi = acos(-1);
// For use with integers, just set eps=0 and everything remains the same
bool geq(ld a, ld b){return a-b >= -eps;} //a >= b
bool leq(ld a, ld b){return b-a >= -eps;} //a <= b
bool ge(ld a, ld b){return a-b > eps;} //a > b
bool le(ld a, ld b){return b-a > eps;} //a < b
bool eq(ld a, ld b){return abs(a-b) <= eps;} //a == b
bool neq(ld a, ld b){return abs(a-b) > eps;} //a != b
struct point{
ld x, y;
point(): x(0), y(0){}
point(ld x, ld y): x(x), y(y){}
point operator+(const point & p) const{return point(x + p.x, y + p.y);}
point operator-(const point & p) const{return point(x - p.x, y - p.y);}
point operator*(const ld & k) const{return point(x * k, y * k);}
point operator/(const ld & k) const{return point(x / k, y / k);}
point operator+=(const point & p){*this = *this + p; return *this;}
point operator-=(const point & p){*this = *this - p; return *this;}
point operator*=(const ld & p){*this = *this * p; return *this;}
point operator/=(const ld & p){*this = *this / p; return *this;}
point rotate(const ld & a) const{return point(x*cos(a) - y*sin(a), x*sin(a) + y*cos(a));}
point perp() const{return point(-y, x);}
ld ang() const{
ld a = atan2l(y, x); a += le(a, 0) ? 2*pi : 0; return a;
}
ld dot(const point & p) const{return x * p.x + y * p.y;}
ld cross(const point & p) const{return x * p.y - y * p.x;}
ld norm() const{return x * x + y * y;}
ld length() const{return sqrtl(x * x + y * y);}
point unit() const{return (*this) / length();}
bool operator==(const point & p) const{return eq(x, p.x) && eq(y, p.y);}
bool operator!=(const point & p) const{return !(*this == p);}
bool operator<(const point & p) const{return le(x, p.x) || (eq(x, p.x) && le(y, p.y));}
bool operator>(const point & p) const{return ge(x, p.x) || (eq(x, p.x) && ge(y, p.y));}
bool half(const point & p) const{return le(p.cross(*this), 0) || (eq(p.cross(*this), 0) && le(p.dot(*this), 0));}
};
istream &operator>>(istream &is, point & p){return is >> p.x >> p.y;}
ostream &operator<<(ostream &os, const point & p){return os << "(" << p.x << ", " << p.y << ")";}
int sgn(ld x){
if(ge(x, 0)) return 1;
if(le(x, 0)) return -1;
return 0;
}
struct plane{
point a, v;
plane(): a(), v(){}
plane(const point& a, const point& v): a(a), v(v){}
point intersect(const plane& p) const{
ld t = (p.a - a).cross(p.v) / v.cross(p.v);
return a + v*t;
}
bool outside(const point& p) const{ // test if point p is strictly outside
return le(v.cross(p - a), 0);
}
bool inside(const point& p) const{ // test if point p is inside or in the boundary
return geq(v.cross(p - a), 0);
}
bool operator<(const plane& p) const{ // sort by angle
auto lhs = make_tuple(v.half({1, 0}), ld(0), v.cross(p.a - a));
auto rhs = make_tuple(p.v.half({1, 0}), v.cross(p.v), ld(0));
return lhs < rhs;
}
bool operator==(const plane& p) const{ // paralell and same directions, not really equal
return eq(v.cross(p.v), 0) && ge(v.dot(p.v), 0);
}
};
vector<point> halfPlaneIntersection(vector<plane> planes){
planes.push_back({{0, -inf}, {1, 0}});
planes.push_back({{inf, 0}, {0, 1}});
planes.push_back({{0, inf}, {-1, 0}});
planes.push_back({{-inf, 0}, {0, -1}});
sort(planes.begin(), planes.end());
planes.erase(unique(planes.begin(), planes.end()), planes.end());
deque<plane> ch;
deque<point> poly;
for(const plane& p : planes){
while(ch.size() >= 2 && p.outside(poly.back())) ch.pop_back(), poly.pop_back();
while(ch.size() >= 2 && p.outside(poly.front())) ch.pop_front(), poly.pop_front();
if(p.v.half({1, 0}) && poly.empty()) return {};
ch.push_back(p);
if(ch.size() >= 2) poly.push_back(ch[ch.size()-2].intersect(ch[ch.size()-1]));
}
while(ch.size() >= 3 && ch.front().outside(poly.back())) ch.pop_back(), poly.pop_back();
while(ch.size() >= 3 && ch.back().outside(poly.front())) ch.pop_front(), poly.pop_front();
poly.push_back(ch.back().intersect(ch.front()));
return vector<point>(poly.begin(), poly.end());
}
ld f(point a, point b, point c){
ld w = abs((b - a).cross(c - a)) / 2, at = 1;
if((b - c).length() <= eps) return 0;
ld h = w * 2 / (b - c).length(), mx = max((b - a).length(), (c - a).length());
ld v = sqrt(mx * mx - h * h); ld u = v - (b - c).length();
if((b - a).cross(c - a) <= 0) at = -1;
return h * (v - u) * (3 * h * h + u * u + u * v + v * v) / 12 * at;
}
pair<point, point> bisector(point p0, point p1){
point pm = (p0 + p1) / 2;
point b = ((p0 - p1).perp()).unit();
//if(pm.cross(p0 - b) < -eps) b = b * -1;
return {pm, b};
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int ax, ay, bx, by; cin>>ax>>ay>>bx>>by;
point i0(ax, ay), i1(bx, ay), i2(bx, by), i3(ax, by);
int n; cin>>n;
vector<point> v(n);
for(int i = 0; i < n; i++){
int a, b; cin>>a>>b; v[i] = point(a, b);
}
//Computar el voronoi para puntos mas cercanos y lejanos
ld ans = 0;
//Mas cercano
for(int i = 0; i < n; i++){
vector<plane> vp;
for(int j = 0; j < n; j++){
if(i == j) continue;
auto u = bisector(v[i], v[j]);
//cout<<u.fi<<" "<<u.se<<'\n';
vp.pb(plane(u.fi, u.se));
}
vp.pb(plane(i0, i1 - i0)); vp.pb(plane(i1, i2 - i1)); vp.pb(plane(i2, i3 - i2)); vp.pb(plane(i3, i0 - i3));
auto u = halfPlaneIntersection(vp);
//cout<<"Region de Voronoi para el punto "<<v[i]<<'\n';
//for(auto e : u) cout<<e<<" "; cout<<'\n';
for(int j = 0; j < u.size(); j++){
int l = j + 1; if(l == u.size()) l = 0;
ans -= f(v[i], u[j], u[l]);
}
}
//Mas lejano
for(int i = 0; i < n; i++){
vector<plane> vp;
for(int j = 0; j < n; j++){
if(i == j) continue;
auto u = bisector(v[i], v[j]);
vp.pb(plane(u.fi, u.se * -1));
}
vp.pb(plane(i0, i1 - i0)); vp.pb(plane(i1, i2 - i1)); vp.pb(plane(i2, i3 - i2)); vp.pb(plane(i3, i0 - i3));
auto u = halfPlaneIntersection(vp);
for(int j = 0; j < u.size(); j++){
int l = j + 1; if(l == u.size()) l = 0;
ans += f(v[i], u[j], u[l]);
}
}
cout<<setprecision(35)<<abs(ans) * pi / (bx - ax) / (by - ay);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
0 0 2 2 2 3 1 1 3
output:
8.3775804095727816438177182334356985
result:
ok found '8.3775804', expected '8.3775804', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
0 0 2 2 2 5 1 1 3
output:
37.699111843077517395445008574483836
result:
ok found '37.6991118', expected '37.6991118', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2084ms
memory: 4168kb
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:
6657168.1428533856878857477568089962
result:
ok found '6657168.1428534', expected '6657168.1428534', error '0.0000000'
Test #4:
score: 0
Accepted
time: 2104ms
memory: 4104kb
input:
-3013 5287 7654 9132 2000 -19 49 -17 -35 64 68 48 -49 -72 -14 29 -93 -13 -8 -80 11 39 88 -31 82 68 -66 5 41 -74 -8 0 15 11 34 69 -12 15 -86 5 -78 -48 73 10 9 -2 8 81 52 41 -43 -45 -41 -23 60 -40 -45 -26 27 -32 73 8 -20 2 91 46 17 51 -66 -65 -32 37 -9 58 63 -14 -31 60 -56 -85 -22 9 -66 -7 -53 -21 40 ...
output:
10130702.494014989879360655322670937
result:
ok found '10130702.4940150', expected '10130702.4940150', error '0.0000000'
Test #5:
score: 0
Accepted
time: 2144ms
memory: 4036kb
input:
-5561 9559 6905 9930 2000 79 338 2 214 325 -193 -390 -157 -517 943 -759 970 449 901 -369 636 -661 -211 847 -558 223 -564 185 822 -656 -854 -991 -617 -422 -169 -63 -799 327 -911 -960 945 -948 831 -494 93 266 -299 139 -535 796 707 75 -146 10 566 72 -713 -132 -341 348 924 -739 -838 982 995 -445 500 -71...
output:
158891446.62387780114659108221530914
result:
ok found '158891446.6238778', expected '158891446.6238778', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2204ms
memory: 4108kb
input:
-5245 -7558 1275 934 2000 -40 125 79 -30 49 13 -127 153 -151 -28 -82 -140 147 131 123 -105 -84 71 -49 -146 -140 82 57 172 -140 -32 -173 24 -55 -101 44 142 -68 -114 122 69 -137 66 19 199 31 109 -161 -66 63 -101 65 -114 166 -66 83 -162 60 70 -19 -134 15 161 -130 22 -130 50 8 -121 150 89 132 44 -131 -3...
output:
11172638.258339251064171548932790756
result:
ok found '11172638.2583393', expected '11172638.2656236', error '0.0000000'
Test #7:
score: 0
Accepted
time: 2062ms
memory: 4080kb
input:
-7167 6117 -3297 6866 2000 -346 -144 -227 169 -168 -373 -63 -227 -24 405 -232 -163 295 22 222 351 293 41 -335 260 -43 -426 -205 193 163 -284 -406 284 -202 -114 -339 -86 -413 17 -237 -394 -333 -145 -104 416 -478 -53 451 102 85 58 -124 -472 424 -88 394 243 -459 45 12 -490 -9 465 -159 -202 315 -272 -24...
output:
52361392.515027465084131108596920967
result:
ok found '52361392.5150275', expected '52361392.5150275', error '0.0000000'
Test #8:
score: 0
Accepted
time: 2182ms
memory: 4000kb
input:
-6462 -5871 5937 5853 2000 386 236 -108 937 -722 354 -710 -475 462 613 -884 446 595 -675 168 394 -744 -551 761 -399 -688 258 -53 104 -614 -177 -273 -678 794 -15 224 -911 -146 -216 53 633 2 -664 202 -440 24 437 495 623 -297 682 -520 -48 598 720 -7 353 163 744 557 13 395 588 -157 -672 631 -705 -68 818...
output:
57605018.445671099445462459698319435
result:
ok found '57605018.4456711', expected '57605018.8701164', error '0.0000000'
Test #9:
score: 0
Accepted
time: 2094ms
memory: 4160kb
input:
792 4703 2923 5458 2000 7281 5289 -5154 2943 -8483 3113 9380 -576 -2191 -291 -8200 898 -192 4724 1161 441 34 3999 8544 3576 -5481 4273 -9792 9565 4854 1262 4254 -3376 -5778 9480 8631 -2225 7129 2187 5344 7740 2975 6174 -2919 -7172 7990 -5117 -6823 -7233 5020 5269 -9874 1051 8841 4586 -3612 -7483 644...
output:
1133083681.5454701491398736834526062
result:
ok found '1133083681.5454702', expected '1133083681.5454702', error '0.0000000'
Test #10:
score: 0
Accepted
time: 2105ms
memory: 4096kb
input:
-4075 7303 -1671 8073 2000 -10 305 -1105 -119 -238 205 -1206 -482 943 -89 -1578 223 -520 1158 21 1622 -621 -886 -163 -515 283 1802 36 -1410 213 -1921 -1539 -231 835 148 56 1448 -407 1653 1896 -533 1321 -437 530 172 132 18 1260 586 -363 -220 989 1353 281 -1907 -1116 -801 695 592 1221 -983 1731 -939 -...
output:
205950762.73416204357636161148548126
result:
ok found '205950762.7341620', expected '205950762.7341621', error '0.0000000'
Test #11:
score: 0
Accepted
time: 2129ms
memory: 4160kb
input:
2121 3865 3457 7582 2000 3902 -1511 -1817 504 -3515 3188 -4470 211 536 1795 2230 -1512 3979 297 2430 901 2368 2525 -2553 -252 476 2279 -3859 2565 -754 396 3358 2726 4787 -664 173 1056 -1154 -1556 -2442 -406 -1838 976 3785 1136 -131 -421 77 4058 3773 2965 1333 -622 4188 -2571 -624 -2051 -1965 4268 -1...
output:
399702074.05400643535540439188480377
result:
ok found '399702074.0540065', expected '399702074.0540065', error '0.0000000'
Test #12:
score: 0
Accepted
time: 2150ms
memory: 4100kb
input:
5377 -2525 9878 7241 2000 316 9854 1690 3184 -9795 -898 -7924 3181 -2410 1478 -3849 -8880 8447 -487 3826 -2478 1445 -2923 5459 677 8830 -3598 1045 -5139 7231 -6856 -4410 4982 -3180 -2528 -7891 -4137 6686 -3732 -6102 -1926 6562 5714 4562 -5710 223 -9921 2609 -3935 8187 55 -5017 -4465 -1387 -2695 6015...
output:
1061816977.6676594661548733711242676
result:
ok found '1061816977.6676595', expected '1061816977.6676595', error '0.0000000'
Test #13:
score: 0
Accepted
time: 2288ms
memory: 4304kb
input:
-3243 -8661 4122 -2937 2000 1 7637 0 1870 1 7982 -1 -391 0 -4347 -1 2035 0 -2623 0 6943 0 1511 0 -8789 -1 7213 1 -4998 1 -8958 1 -182 -1 -318 1 3712 0 -3215 1 -5210 1 6983 -1 -2567 1 -470 -1 7652 0 -2394 1 7196 1 280 1 5785 1 545 1 8779 1 1 1 -9675 1 5137 -1 -1160 1 -3955 0 3176 0 -6143 0 519 1 5678...
output:
791760973.95850037876516580581665039
result:
ok found '791760973.9585004', expected '791760973.9585004', error '0.0000000'
Test #14:
score: 0
Accepted
time: 2175ms
memory: 4340kb
input:
-4763 3483 5561 3747 2000 -3915 1 8391 -1 -4112 0 5453 -1 -8775 1 -2182 0 -3819 1 -2702 1 -7119 1 1279 0 7959 -1 -4345 0 -1024 1 -4853 -1 -2637 1 -2136 -1 -9603 -1 -5869 1 -1765 1 -3625 1 9255 0 4677 1 4660 -1 3250 1 -8156 -1 -2988 0 8492 1 -961 0 9331 -1 -1913 1 -3152 0 8877 -1 8390 0 3420 0 -7929 ...
output:
505360943.97037652693688869476318359
result:
ok found '505360943.9703766', expected '505360943.9703766', error '0.0000000'
Test #15:
score: 0
Accepted
time: 2153ms
memory: 4272kb
input:
-8627 -2766 -1956 4443 2000 -4 -9231 -6 -3132 4 176 1 8378 1 6264 -3 -9699 -10 -6369 -9 -4283 -7 7401 1 -1418 7 -5096 7 -7114 -4 -3937 2 5922 -1 6133 6 -8932 -6 3552 2 4767 9 7643 3 4129 4 2295 -5 8379 1 768 -10 -8915 5 4022 -6 -6665 4 4425 -3 6046 6 3827 -5 3831 -6 -6224 5 9807 9 11 5 4503 -6 -5911...
output:
448946370.79278799911844544112682343
result:
ok found '448946370.7927880', expected '448946370.7927880', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2114ms
memory: 4260kb
input:
-4229 -9182 1776 -5186 2000 8444 3 3252 6 -7072 5 5793 -1 1339 2 -3500 6 -9676 -4 -1101 -8 -4997 7 462 -6 1476 7 -1331 9 561 -4 -951 -6 -466 -8 -8455 2 8033 -5 2982 9 -7803 6 8473 1 674 5 -7228 -1 -1891 -10 -3408 -7 -917 -8 9486 -5 355 9 1212 -4 3712 10 9106 1 9958 1 7446 -5 8816 -1 -1752 4 4285 0 -...
output:
438654068.21846062308759428560733795
result:
ok found '438654068.2184606', expected '438654068.2184606', error '0.0000000'
Test #17:
score: -100
Wrong Answer
time: 2131ms
memory: 4000kb
input:
-6880 -3012 949 2588 2000 56 -2490 59 -8874 -90 7871 -48 9340 -29 -4546 72 1776 -22 -8437 -7 5228 6 -2206 89 -5714 71 -6149 44 8645 -17 -8800 19 -8446 -31 -1438 58 4422 -10 -6275 98 -7180 21 -3721 14 3061 -60 -2084 45 4628 -57 -7683 -19 -5389 97 4046 58 5141 -44 288 49 -3579 -39 -7224 94 5901 -68 -3...
output:
411571504.53789106133626773953437805
result:
wrong answer 1st numbers differ - expected: '411858700.0432993', found: '411571504.5378911', error = '0.0006973'