QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#368411 | #8513. Insects, Mathematics, Accuracy, and Efficiency | ucup-team134# | WA | 22ms | 4360kb | C++17 | 2.7kb | 2024-03-27 03:27:03 | 2024-03-27 03:27:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ldb double
#define pb push_back
#define mp make_pair
struct pt{
ldb x,y;
pt():x(0),y(0){}
pt(ldb a,ldb b):x(a),y(b){}
};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
pt operator - (pt a){return pt(-a.x,-a.y);}
pt operator + (pt a,pt b){return pt(a.x+b.x,a.y+b.y);}
pt operator * (pt a,ldb b){return pt(a.x*b,a.y*b);}
pt operator / (pt a,ldb b){return pt(a.x/b,a.y/b);}
pt perp(pt a){return pt(-a.y,a.x);}
ldb cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ldb dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
ldb abs(pt a){return sqrt(dot(a,a));}
int part(pt a){return a.y<0 || (a.y==0 && a.x<0);}
bool operator < (pt a,pt b){return tie(a.x,a.y)<tie(b.x,b.y);}
const int N=10050;
pt pts[N];
vector<pt> ConvexHull(int n){
sort(pts+1,pts+1+n);
vector<pt> hull;
int sz=0;
for(int t=0;t<2;t++){
int was=sz;
for(int i=1;i<=n;i++){
while(sz>was+1 && cross(hull[sz-1]-hull[sz-2],pts[i]-hull[sz-2])<=0){
hull.pop_back();
sz--;
}
hull.pb(pts[i]);
sz++;
}
hull.pop_back();
sz--;
reverse(pts+1,pts+1+n);
}
return hull;
}
void Inter(pt a,pt b,ldb r,vector<pt>& cand){
pt v=b-a;
ldb d=cross(v,a)/abs(v);
pt h=-perp(v);
h=h/abs(h)*d;
ldb len=sqrt(max(0.0,r*r-d*d));
cand.pb(h+v/abs(v)*len);
cand.pb(h-v/abs(v)*len);
}
int main(){
int n,r;
scanf("%i %i",&n,&r);
for(int i=1;i<=n;i++){
int x,y;
scanf("%i %i",&x,&y);
pts[i]=pt(x,y);
}
vector<pt> hull=ConvexHull(n);
if(hull.size()<2){
printf("0.0\n");
return 0;
}
vector<pt> cand;
for(int i=0;i<hull.size();i++){
Inter(hull[i],hull[(i+1)%hull.size()],r,cand);
Inter(pt(0,0),perp(hull[i]-hull[(i+1)%hull.size()]),r,cand);
}
//printf("Hull ");
//for(pt p:hull)printf("(%lf, %lf) ",p.x,p.y);
//printf("\n");
sort(cand.begin(),cand.end(),[&](pt a,pt b){return mp(part(a),0.0)<mp(part(b),cross(a,b));});
int L=0,R=0;
auto nxt=[&](int x){return (x+1)%hull.size();};
auto pre=[&](int x){return (x-1+hull.size())%hull.size();};
ldb ans=0;
for(int i=0;i<hull.size();i++){
ans+=cross(hull[i],hull[nxt(i)]);
}
ans=abs(ans)/2;
for(pt p:cand){
//printf("(%lf, %lf)\n",p.x,p.y);
while(cross(hull[L]-p,hull[nxt(L)]-p)<0)L=nxt(L);
while(cross(hull[L]-p,hull[pre(L)]-p)<0)L=pre(L);
while(cross(hull[R]-p,hull[nxt(R)]-p)>0)R=nxt(R);
while(cross(hull[R]-p,hull[pre(R)]-p)>0)R=pre(R);
//printf("L(%lf, %lf) R(%lf, %lf)\n",hull[L].x,hull[L].y,hull[R].x,hull[R].y);
ldb now=0;
for(int i=L;i!=R;i=nxt(i)){
now+=cross(hull[i],hull[nxt(i)]);
}
now+=cross(hull[R],p);
now+=cross(p,hull[L]);
now=abs(now)/2;
//printf("%lf\n",now);
ans=max(ans,now);
}
printf("%.12lf\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4028kb
input:
4 1000 -1000 0 0 0 1000 0 0 -1000
output:
2000000.000000000000
result:
ok found '2000000.000000000', expected '2000000.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
2 100 17 7 19 90
output:
4849.704644437563
result:
ok found '4849.704644438', expected '4849.704644438', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 4160kb
input:
1 100 13 37
output:
0.0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
4 1000 -800 600 800 600 -800 -600 800 -600
output:
2240000.000000000000
result:
ok found '2240000.000000000', expected '2240000.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3988kb
input:
3 1000 200 400 -600 -400 400 -800
output:
1045685.424949237844
result:
ok found '1045685.424949238', expected '1045685.424949238', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4056kb
input:
4 1000 200 -600 600 -400 800 -600 0 -800
output:
732310.562561766012
result:
ok found '732310.562561766', expected '732310.562561766', error '0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4032kb
input:
4 1000 -600 700 -300 900 0 800 -800 400
output:
892213.595499957912
result:
ok found '892213.595499958', expected '892213.595499958', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3932kb
input:
5 1000 -300 -200 -200 -400 -100 -700 -800 -500 -500 -300
output:
619005.494464025949
result:
ok found '619005.494464026', expected '619005.494464026', error '0.000000000'
Test #9:
score: -100
Wrong Answer
time: 22ms
memory: 4360kb
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:
314026590.136600553989
result:
wrong answer 1st numbers differ - expected: '314026591.7801104', found: '314026590.1366006', error = '0.0000000'