AcWing 2935. 信用卡凸包
原题链接
中等
作者:
溪染
,
2021-01-20 19:14:47
,
所有人可见
,
阅读 727
#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
struct point{
double x,y;
point(){};
point(double x,double y):x(x),y(y){};
double operator%(point b){
return x*b.y-y*b.x;
}
point operator-(point b){
return point(x-b.x,y-b.y);
}
point operator+(point b){
return point(x+b.x,y+b.y);
}
point rotate(double s){
return point(x*cos(s)-y*sin(s),y*cos(s)+x*sin(s));
}
bool operator<(point b){
return x<b.x;
}
}p[40010];
double distanc(point a,point b)
{
return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
int n;
double a,b,r;
int stk[40010];
bool uers[40010];
double work()
{
int tp=0;
sort(p+1,p+n+1);
for(int i=1;i<=n;i++){
while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]]) % (p[i]-p[stk[tp-1]]))>=0)
uers[stk[tp--]]=0;
uers[i]=1;
stk[++tp]=i;
}
uers[1]=0;
for(int i=n;i>=1;i--){
if(uers[i]) continue;
while(tp>=2&&((p[stk[tp]]-p[stk[tp-1]]) % (p[i]-p[stk[tp-1]]))>=0)
tp--;
stk[++tp]=i;
}
double ans=0;
for(int i=2;i<=tp;i++)
ans+=distanc(p[stk[i]],p[stk[i-1]]);
return ans;
}
int main()
{
cin>>n;
cin>>b>>a>>r;
for(int i=1;i<=n;i++){
double x,y,s;
scanf("%lf%lf%lf",&x,&y,&s);
point st=point(x,y);
p[4*i-3]=st+point(a/2-r,b/2-r).rotate(s);
p[4*i-2]=st+point(-a/2+r,b/2-r).rotate(s);
p[4*i-1]=st+point(a/2-r,-b/2+r).rotate(s);
p[4*i-0]=st+point(-a/2+r,-b/2+r).rotate(s);
}
n=4*n;
printf("%.2lf",work()+acos(-1)*r*2);
return 0;
}
%%%%%%%%%%%%%%