QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402612#7783. Military ManeuverJose_17WA 2288ms4340kbC++206.6kb2024-05-01 01:49:552024-05-01 01:49:55

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 01:49:55]
  • 评测
  • 测评结果:WA
  • 用时:2288ms
  • 内存:4340kb
  • [2024-05-01 01:49:55]
  • 提交

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'