QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#367558#8513. Insects, Mathematics, Accuracy, and EfficiencyJose_17WA 171ms4196kbC++207.0kb2024-03-26 07:14:062024-03-26 07:14:06

Judging History

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

  • [2024-03-26 07:14:06]
  • 评测
  • 测评结果:WA
  • 用时:171ms
  • 内存:4196kb
  • [2024-03-26 07:14:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// Holi c:

#define ll long long int
//#define ld long double
#define ii __int128
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(), v.end()

const int Inf = 1e9;
const ll mod =  1e9 + 7;
const ll INF = 1e18;
const int maxn = 2e5 + 5;

using ld = long double;
const ld eps = 1e-12, inf = numeric_limits<ld>::max(), 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) ? pi * 2 : 0;
        return a;
	}
    ld ang(const point & p) const{ return abs(ang() - p.ang()); }
	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));}
};

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;
}

void polarSort(vector<point> & P, const point & o, const point & v){
	//sort points in P around o, taking the direction of v as first angle
	sort(P.begin(), P.end(), [&](const point & a, const point & b){
		return point((a - o).half(v), 0) < point((b - o).half(v), (a - o).cross(b - o));
	});
}

vector<point> convexHull(vector<point> P){
	sort(P.begin(), P.end());
	vector<point> L, U;
	for(int i = 0; i < P.size(); i++){
		while(L.size() >= 2 && leq((L[L.size() - 2] - P[i]).cross(L[L.size() - 1] - P[i]), 0)){
			L.pop_back();
		}
		L.push_back(P[i]);
	}
	for(int i = P.size() - 1; i >= 0; i--){
		while(U.size() >= 2 && leq((U[U.size() - 2] - P[i]).cross(U[U.size() - 1] - P[i]), 0)){
			U.pop_back();
		}
		U.push_back(P[i]);
	}
	L.pop_back();
	U.pop_back();
	L.insert(L.end(), U.begin(), U.end());
	return L;
}

ld area(vector<point> & P){
	int n = P.size();
	ld ans = 0;
	for(int i = 0; i < n; i++){
		ans += P[i].cross(P[(i + 1) % n]);
	}
	return abs(ans / 2);
}

vector<point> intersectLineCircle(const point & a, const point & v, const point & c, ld r){
	//line a+tv, circle with center c and radius r
	ld h2 = r*r - v.cross(c - a) * v.cross(c - a) / v.norm();
	point p = a + v * v.dot(c - a) / v.norm();
	if(eq(h2, 0)) return {p}; //line tangent to circle
	else if(le(h2, 0)) return {}; //no intersection
	else{
		point u = v.unit() * sqrt(h2);
		return {p - u, p + u}; //two points of intersection (chord)
	}
}

ld f1(point p0, point p1, point p2){
    return abs((p1 - p0).cross(p2 - p0)) / 2;
}

ld f(point p0, point p1, point t1, point t2){
    ld ans = 0, l = 0, r = 0;
    
    //r = (p0).ang(p1);
    r = acosl(p1.dot(p0) / p1.length() / p0.length());
    
    point rt = p1.rotate(r);
    if(!(abs(rt.x - p0.x) <= 0.85 && abs(rt.y - p0.y) <= 0.85)) r = 2 * pi - r;
    
    //cout<<r<<'\n';
    for(int i = 0; i < 500; i++){
        ld m1 = l + (r - l) / 3, m2 = r - (r - l) / 3;
        ld w1 = f1(t1, t2, p1.rotate(m1)), w2 = f1(t1, t2, p1.rotate(m2));
        if(w1 < w2) l = m1;
        else r = m2;
    }
    return f1(t1, t2, p1.rotate(l));
}

ld calc(point p0, point p1, int t0, int t1, vector<point> & v){
    ld ans = f(p0, p1, v[t0], v[t1]);
    return ans;
}

ld solveto2(point p0, point p1, point p2, point p3){
    return max(f(p0, p1, p2, p3), f(p1, p0, p3, p2));
}


int main(){
	ios_base::sync_with_stdio(false);  cin.tie(NULL); cout.tie(0);
	int n; ld r; cin>>n>>r; r += eps;
	vector<point> v(n);
	for(int i = 0; i < n; i++){ int a, b; cin>>a>>b; v[i] = point(a, b); }
	if(n == 1){ cout<<0<<'\n'; return 0; }
	sort(all(v));
	v = convexHull(v); n = v.size(); ld res = area(v); reverse(all(v));
	vector<point> side;
	for(int i = 0; i < v.size(); i++){
	    auto u = intersectLineCircle(v[i], v[(i + 1) % (int)v.size()] - v[i], point(0, 0), r);
	    if(n == 2 && i + 1 == v.size()) continue;
	    side.pb(u[0]); side.pb(u[1]);
	}
	polarSort(side, point(0, 0), point(-1, 0));
	reverse(all(side)); vector<point> u; u.pb(v[v.size() - 1]); for(int i = 0; i < v.size() - 1; i++) u.pb(v[i]); v = u;
	//for(auto e : side) cout<<e<<" | "; cout<<'\n'<<"-------------"<<'\n';
	//for(auto e : v) cout<<e<<" | "; cout<<'\n'<<"--------------------------------"<<'\n';
	int j = 0, l = 0, m = side.size(); n = v.size(); ld ans = 0, zes = 0;
	if(n == 2){ cout<<setprecision(20)<<solveto2(side[0], side[1], v[0], v[1])<<'\n'; return 0; }
	//Obtener las tangentes de cada intervalo
	for(int i = 0; i < m; i++){
	    //if(side[i] == side[(i + 1) % m]) continue;
	    while((v[l] - side[i]).cross(v[(l + 1) % n] - side[i]) < eps){
	        if(i) zes -= f1(v[j], v[l], v[(l + 1) % n]);
	        l++; if(l == n) l = 0;
	    }
	    //cout<<zes<<" v ";
	    while((v[j] - side[(i + 1) % m]).cross(v[(j + 1) % n] - side[(i + 1) % m]) > -eps){
	        zes += f1(v[l], v[j], v[(j + 1) % n]);
	        j++; if(j == n) j = 0;
	    }
	    if(abs((v[j] - side[(i + 1) % m]).cross(v[(j - 1 + n) % n] - side[(i + 1) % m])) <= eps){
	        j--;
	        if(j < 0) j += n;
	        zes -= f1(v[l], v[j], v[(j + 1) % n]);
	    }
	    
	    //cout<<zes<<'\n';
	    //cout<<"Intervalo: "<<side[i]<<" , "<<side[(i + 1) % m]<<" Con las tangentes en: "<<v[l]<<" , "<<v[j]<<" Con area de "<<calc(side[i], side[(i + 1) % m], l, j, v)<<" , "<<zes<<'\n';
	    ans = max(ans, calc(side[i], side[(i + 1) % m], l, j, v) - abs(zes));
	    //cout<<res+ans<<'\n';
	}
	cout<<setprecision(20)<<res + ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4104kb

input:

4 1000
-1000 0
0 0
1000 0
0 -1000

output:

2000000.000000001

result:

ok found '2000000.000000001', expected '2000000.000000000', error '0.000000000'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

2 100
17 7
19 90

output:

4849.7046444376052525

result:

ok found '4849.704644438', expected '4849.704644438', error '0.000000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

1 100
13 37

output:

0

result:

ok found '0.000000000', expected '0.000000000', error '-0.000000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 4008kb

input:

4 1000
-800 600
800 600
-800 -600
800 -600

output:

2240000.0000000007999

result:

ok found '2240000.000000001', expected '2240000.000000000', error '0.000000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4012kb

input:

3 1000
200 400
-600 -400
400 -800

output:

1045685.4249492385852

result:

ok found '1045685.424949239', expected '1045685.424949238', error '0.000000000'

Test #6:

score: 0
Accepted
time: 3ms
memory: 3988kb

input:

4 1000
200 -600
600 -400
800 -600
0 -800

output:

732310.5625617664673

result:

ok found '732310.562561766', expected '732310.562561766', error '0.000000000'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3928kb

input:

4 1000
-600 700
-300 900
0 800
-800 400

output:

892213.59549995838648

result:

ok found '892213.595499958', expected '892213.595499958', error '0.000000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3804kb

input:

5 1000
-300 -200
-200 -400
-100 -700
-800 -500
-500 -300

output:

619005.49446402627751

result:

ok found '619005.494464026', expected '619005.494464026', error '0.000000000'

Test #9:

score: 0
Accepted
time: 107ms
memory: 4048kb

input:

1000 10000
-9998 -136
-9996 -245
-9995 -280
-9993 -347
-9991 -397
-9989 -440
-9985 -525
-9984 -545
-9983 -564
-9981 -599
-9979 -632
-9973 -721
-9971 -747
-9966 -810
-9963 -846
-9957 -916
-9953 -958
-9948 -1008
-9945 -1037
-9938 -1103
-9927 -1196
-9920 -1253
-9913 -1308
-9908 -1346
-9891 -1465
-9874 ...

output:

314026591.7801103541

result:

ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

2 10000
-9999 0
-9998 -1

output:

12070.56781186547595

result:

ok found '12070.567811865', expected '12070.567811865', error '0.000000000'

Test #11:

score: 0
Accepted
time: 171ms
memory: 4196kb

input:

1604 10000
2604 -9655
7380 -6748
9963 859
9843 1765
-1452 9894
-2024 9793
-8862 4633
-2604 -9655
9301 3673
9871 -1601
-565 -9984
9640 -2659
9312 3645
-8291 -5591
7879 6158
1301 9915
509 9987
7757 -6311
-9301 -3673
7702 -6378
5415 8407
-9971 761
9023 -4311
-6785 7346
-9852 1714
-9788 -2048
9819 -1894...

output:

314156571.11234992856

result:

ok found '314156571.112349927', expected '314156571.112349927', error '0.000000000'

Test #12:

score: 0
Accepted
time: 151ms
memory: 4088kb

input:

1444 10000
3378 8342
-734 8970
-3168 8424
1741 8830
-3631 8235
-6622 -6095
8605 -2637
-3762 8176
-8509 2932
-8915 1234
-1919 -8793
-7663 -4720
3040 -8471
-7357 5184
5746 -6927
5827 -6859
6519 6205
328 -8994
-5282 7287
4797 -7615
-5505 7120
-2733 8575
6902 5776
-4666 7696
6946 5723
-4154 7984
6644 60...

output:

257163269.62953050128

result:

ok found '257163269.629530489', expected '257163269.629530489', error '0.000000000'

Test #13:

score: 0
Accepted
time: 145ms
memory: 4152kb

input:

1396 10000
-5817 -5492
-692 -7970
-6967 -3932
-6316 -4910
-6562 4576
-7358 3140
2376 7639
-7883 1363
-2337 7651
-6950 -3962
-6927 4002
4961 -6276
5036 6216
7274 3330
-6976 3916
1490 7860
-2816 7488
-6927 -4002
-3107 7372
-6802 4211
4353 6712
-5594 -5719
875 -7952
-2943 7439
-4672 6494
-4405 -6678
-3...

output:

207875930.5000000048

result:

ok found '207875930.500000000', expected '207875930.500000000', error '0.000000000'

Test #14:

score: 0
Accepted
time: 130ms
memory: 4168kb

input:

1252 10000
-6409 2815
5515 4311
6506 2583
4459 5396
2493 6541
-3215 6218
2911 -6366
0 -7000
658 6969
312 -6993
-1100 -6913
6621 2272
-1081 -6916
-6901 1173
-658 6969
5227 -4656
2911 6366
6715 -1977
3812 5871
1015 -6926
6061 3502
-473 6984
5079 -4817
614 -6973
-2667 6472
1446 6849
-1791 -6767
-2004 -...

output:

164951741.65765437699

result:

ok found '164951741.657654375', expected '164951741.657654375', error '0.000000000'

Test #15:

score: 0
Accepted
time: 5ms
memory: 4104kb

input:

42 10000
-800 -8
-799 -40
-730 -247
-599 -399
-591 -406
-541 -443
-283 -562
-189 -584
-43 -600
223 -577
507 -464
575 -417
607 -391
654 -346
677 -320
775 -149
794 -74
726 251
718 264
698 292
689 304
619 380
538 443
331 546
315 551
279 562
237 573
182 584
116 593
52 598
-37 599
-57 598
-238 573
-314 5...

output:

8755559.4805068884689

result:

ok found '8755559.480506888', expected '8755559.480506888', error '0.000000000'

Test #16:

score: 0
Accepted
time: 17ms
memory: 4056kb

input:

171 10000
-800 -29
-794 -79
-788 -108
-785 -120
-776 -149
-775 -152
-768 -171
-748 -215
-745 -221
-738 -234
-709 -280
-704 -287
-695 -299
-688 -308
-679 -319
-667 -333
-660 -341
-631 -370
-607 -392
-593 -404
-583 -412
-564 -427
-546 -440
-527 -453
-458 -493
-422 -511
-378 -530
-360 -537
-329 -548
-2...

output:

8773418.7784261353863

result:

ok found '8773418.778426135', expected '8773418.778426135', error '0.000000000'

Test #17:

score: 0
Accepted
time: 20ms
memory: 4020kb

input:

202 10000
-900 -43
-898 -70
-895 -103
-894 -111
-890 -140
-888 -152
-873 -223
-868 -242
-862 -263
-856 -281
-835 -339
-826 -360
-812 -391
-805 -405
-793 -428
-788 -437
-780 -451
-768 -471
-757 -489
-743 -510
-731 -527
-707 -559
-692 -577
-673 -599
-664 -609
-652 -622
-621 -653
-607 -666
-596 -676
-5...

output:

10316038.315566766124

result:

ok found '10316038.315566767', expected '10316038.315566765', error '0.000000000'

Test #18:

score: 0
Accepted
time: 26ms
memory: 4164kb

input:

252 10000
-900 -43
-899 -60
-898 -73
-897 -84
-893 -120
-888 -153
-884 -174
-881 -189
-879 -198
-874 -219
-869 -238
-867 -245
-859 -272
-852 -293
-846 -310
-839 -329
-830 -351
-824 -365
-820 -374
-810 -395
-802 -411
-793 -428
-783 -446
-769 -470
-758 -487
-745 -507
-734 -523
-717 -546
-710 -555
-687...

output:

10316182.050690599491

result:

ok found '10316182.050690599', expected '10316182.050690599', error '0.000000000'

Test #19:

score: 0
Accepted
time: 42ms
memory: 3940kb

input:

404 10000
-4997 -198
-4993 -282
-4982 -433
-4975 -509
-4967 -582
-4962 -623
-4933 -821
-4925 -868
-4915 -924
-4898 -1009
-4881 -1089
-4872 -1128
-4863 -1166
-4838 -1266
-4815 -1351
-4802 -1397
-4779 -1473
-4754 -1552
-4693 -1728
-4666 -1799
-4627 -1898
-4619 -1917
-4592 -1981
-4537 -2104
-4516 -2149...

output:

95669905.972632118668

result:

ok found '95669905.972632125', expected '95669905.972632110', error '0.000000000'

Test #20:

score: 0
Accepted
time: 89ms
memory: 4036kb

input:

888 10000
-9119 -134
-9118 -188
-9117 -234
-9116 -268
-9114 -330
-9113 -357
-9108 -467
-9106 -505
-9102 -573
-9098 -634
-9096 -661
-9092 -714
-9087 -775
-9076 -895
-9070 -953
-9066 -990
-9060 -1044
-9053 -1101
-9045 -1166
-9042 -1190
-9039 -1213
-9030 -1278
-9013 -1393
-9002 -1462
-8996 -1498
-8986 ...

output:

263523679.50841663609

result:

ok found '263523679.508416623', expected '263523679.508416623', error '0.000000000'

Test #21:

score: 0
Accepted
time: 18ms
memory: 4152kb

input:

333 10000
-832 -233
-844 -216
-846 -213
-854 -201
-860 -192
-865 -184
-868 -179
-871 -173
-873 -169
-877 -161
-878 -159
-879 -157
-887 -140
-894 -122
-895 -119
-896 -116
-898 -109
-902 -94
-906 -73
-909 -56
-910 -49
-911 -40
-913 -17
-914 -3
-913 20
-909 74
-908 86
-907 94
-905 109
-902 129
-900 142...

output:

9914565.5701116607306

result:

ok found '9914565.570111660', expected '9914565.570111660', error '0.000000000'

Test #22:

score: 0
Accepted
time: 25ms
memory: 3860kb

input:

414 10000
107 794
158 789
201 784
225 781
238 779
254 776
259 775
264 774
278 771
287 769
304 765
308 764
324 760
328 759
332 758
343 755
350 753
385 743
399 739
409 736
419 733
446 724
452 722
463 718
498 705
514 699
522 696
535 691
561 681
566 679
579 673
587 669
589 668
591 667
601 662
605 660
61...

output:

10783650.256604671078

result:

ok found '10783650.256604671', expected '10783650.256604670', error '0.000000000'

Test #23:

score: 0
Accepted
time: 26ms
memory: 3888kb

input:

666 10000
-294 883
-290 884
-278 887
-270 889
-266 890
-261 891
-246 894
-241 895
-225 898
-219 899
-213 900
-182 905
-175 906
-168 907
-160 908
-150 909
-140 910
-128 911
-116 912
-90 914
-76 915
-39 917
-19 918
1 919
15 918
28 917
40 916
64 914
75 913
93 911
101 910
109 909
124 907
139 905
146 904...

output:

10214064.821868660082

result:

ok found '10214064.821868660', expected '10214064.821868660', error '0.000000000'

Test #24:

score: 0
Accepted
time: 25ms
memory: 4084kb

input:

777 10000
769 412
775 403
777 400
781 394
784 389
788 382
792 375
799 362
800 360
801 358
802 356
803 354
804 352
811 338
812 336
813 334
814 332
816 328
817 326
819 321
824 308
830 292
833 284
836 275
837 272
839 266
840 263
842 257
843 254
844 251
845 248
847 242
848 239
849 236
850 233
851 230
85...

output:

10499024.567478029854

result:

ok found '10499024.567478029', expected '10499024.567478029', error '0.000000000'

Test #25:

score: 0
Accepted
time: 19ms
memory: 4008kb

input:

969 10000
352 -559
348 -560
344 -561
336 -563
328 -565
310 -569
301 -571
296 -572
291 -573
281 -575
276 -576
266 -578
261 -579
256 -580
251 -581
246 -582
230 -585
219 -587
208 -589
191 -592
185 -593
179 -594
173 -595
167 -596
161 -597
154 -598
147 -599
139 -600
131 -601
123 -602
114 -603
101 -604
85...

output:

10610264.590444817213

result:

ok found '10610264.590444818', expected '10610264.590444816', error '0.000000000'

Test #26:

score: 0
Accepted
time: 17ms
memory: 4016kb

input:

1000 10000
-331 734
-328 735
-325 736
-322 737
-319 738
-313 740
-306 742
-299 744
-292 746
-288 747
-284 748
-280 749
-276 750
-268 752
-264 753
-260 754
-252 756
-248 757
-235 760
-226 762
-217 764
-212 765
-207 766
-202 767
-192 769
-187 770
-177 772
-172 773
-167 774
-156 776
-145 778
-128 781
-...

output:

10215997.705076119985

result:

ok found '10215997.705076121', expected '10215997.705076119', error '0.000000000'

Test #27:

score: 0
Accepted
time: 13ms
memory: 4072kb

input:

1000 10000
-545 159
-544 161
-543 163
-542 165
-540 169
-539 171
-537 175
-536 177
-535 179
-534 181
-533 183
-532 185
-530 189
-529 191
-526 196
-523 201
-519 207
-517 210
-515 213
-513 216
-511 219
-508 223
-504 228
-503 229
-502 230
-501 231
-500 232
-498 234
-495 237
-494 238
-493 239
-491 241
-...

output:

8089958.1991278650808

result:

ok found '8089958.199127865', expected '8089958.199127864', error '0.000000000'

Test #28:

score: -100
Wrong Answer
time: 22ms
memory: 4192kb

input:

1000 10000
-674 -603
-678 -598
-682 -593
-686 -588
-690 -583
-693 -579
-696 -575
-699 -571
-702 -567
-711 -555
-717 -547
-720 -543
-725 -536
-730 -529
-735 -522
-737 -519
-739 -516
-741 -513
-743 -510
-745 -507
-747 -504
-749 -501
-753 -495
-758 -487
-761 -482
-764 -477
-768 -470
-772 -463
-780 -449...

output:

10329432.092653032586

result:

wrong answer 1st numbers differ - expected: '10330585.4913332', found: '10329432.0926530', error = '0.0001116'