QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363018 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team052# | RE | 4ms | 4164kb | C++23 | 2.4kb | 2024-03-23 17:55:12 | 2024-03-23 17:55:12 |
Judging History
answer
#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define SZ(x) ((int)(x).size())
#define pb push_back
using namespace std;
#define N 10005
struct Vec
{
double x,y;
Vec(double a=0,double b=0) {x=a,y=b;}
};
const double eps=1e-7;
int sgn(double x)
{
if(x>eps) return 1;
else if(x<-eps) return -1;
return 0;
}
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
double cdot(const Vec &x,const Vec &y) {return x.x+y.x+x.y*y.y;}
double cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
double dis(const Vec &x) {return sqrt(x.x*x.x+x.y*x.y);}
int ccw(const Vec &x,const Vec &y,const Vec &z)
{
int w=sgn(cross(y-x,z-x));
return w;
}
Vec a[N];
int n,st[N+N],tp;
double ans,R;
int main(){
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
cin>>n>>R;
for(int i=1;i<=n;i++) scanf("%lf %lf",&a[i].x,&a[i].y);
int mnx=1;
for(int i=1;i<=n;i++)
{
if(a[i].x<a[mnx].x) mnx=i;
}
swap(a[mnx],a[1]);
sort(a+2,a+n+1,[&](const Vec &x,const Vec &y){
return ccw(a[1],x,y)==-1||(ccw(a[1],x,y)==0&&dis(x-a[1])<dis(y-a[1]));
});
st[++tp]=1;
for(int i=2;i<=n;i++)
{
while(tp>=2&&ccw(a[st[tp-1]],a[st[tp]],a[i])>=0) tp--;
st[++tp]=i;
}
for(int i=1;i<=tp;i++) st[i+tp]=st[i];
assert(tp<=1000);
double S=0;
for(int i=2;i<tp;i++) S+=cross(a[st[i+1]]-a[1],a[st[i]]-a[1]);
S/=2;
// for(int i=1;i<=tp;i++) printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
for(int i=1;i<=tp;i++)
{
double siz=0;
for(int j=i+1;j<i+tp;j++)
{
if(j!=i+1) siz+=cross(a[st[j]]-a[st[i]],a[st[j-1]]-a[st[i]])/2;
double L=dis(a[st[i]]-a[st[j]]);
double gv=R*L+cross(a[st[i]],a[st[j]]); gv/=2;
ans=max(ans,S-siz+gv);
// printf("%d %d : %lf %lf %lf\n",i,j,S,siz,gv);
}
}
printf("%.10lf\n",ans);
return 0;
}
/*
-1000.000000 0.000000
1000.000000 0.000000
0.000000 -1000.000000
1 2 : 1000000.000000 0.000000 1000000.000000
1 3 : 1000000.000000 1000000.000000 1207106.781187
2 3 : 1000000.000000 0.000000 207106.781187
2 4 : 1000000.000000 500000.000000 1000000.000000
3 4 : 1000000.000000 0.000000 207106.781187
3 5 : 1000000.000000 0.000000 1207106.781187
2207106.7811865476
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4164kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.0000000000
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
2 100 17 7 19 90
output:
4849.7046444376
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
1 100 13 37
output:
0.0000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 4044kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000.0000000000
result:
ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.4249492381
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.5625617660
result:
ok found '732310.562561766', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4036kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.5954999579
result:
ok found '892213.595499958', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 4104kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.4944640258
result:
ok found '619005.494464026', expected '619005.494464026', error '0.000000000'
Test #9:
score: 0
Accepted
time: 4ms
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.7801103592
result:
ok found '314026591.780110359', expected '314026591.780110359', error '0.000000000'
Test #10:
score: 0
Accepted
time: 0ms
memory: 4060kb
input:
2 10000 -9999 0 -9998 -1
output:
12070.5678118655
result:
ok found '12070.567811865', expected '12070.567811865', error '0.000000000'
Test #11:
score: -100
Runtime Error
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...