标签：凸包
题目
Description
Input
Output
Sample Input
2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
Sample Output 21.66
HINT
本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为
Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)
#分析
凸包加一个圆的周长，注意建图
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define pi acos(-1)
#define eps 1e-8
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=4e5+6;
double ans,a,b,r;int n,cnt=0,top;
struct P{
double x,y;
P(double xx=0,double yy=0){x=xx,y=yy;}
friend P operator - (P a,P b){return P(a.x-b.x,a.y-b.y);}
friend double operator * (P a,P b){return a.x*b.y-a.y*b.x;}
friend bool operator < (P a,P b){return (fabs(a.y-b.y)<eps)?a.x<b.x:a.y<b.y;}
friend double dis2(P a){return (double)((double)a.x*a.x+(double)a.y*a.y);}
}p[maxn],s[maxn];
struct node{double x,y,angle;}w[maxn];
inline P move(P a,double d,double Angle){return P(a.x+d*cos(Angle),a.y+d*sin(Angle));}
inline bool cmp(P a,P b){return fabs((a-p[1])*(b-p[1]))<eps?dis2(p[1]-a)<dis2(p[1]-b):(a-p[1])*(b-p[1])>0;}
void graham(){
rep(i,1,cnt)if(p[i]<p[1])swap(p[i],p[1]);
sort(p+2,p+cnt+1,cmp);
rep(i,1,cnt){
while(top>1&&(s[top]-s[top-1])*(p[i]-s[top-1])<-eps)top--;
s[++top]=p[i];
}
s[top+1]=s[1];
rep(i,1,top)ans+=sqrt(dis2(s[i]-s[i+1]));
}
int main(){
n=read();
cin>>a>>b>>r;a-=2*r,b-=2*r;
ans+=2*pi*r;
rep(i,1,n)cin>>w[i].x>>w[i].y>>w[i].angle;
rep(i,1,n)
rep(j,0,3){
P t=move(P(w[i].x,w[i].y),b/2,w[i].angle+j*pi/2);
p[++cnt]=move(t,a/2,w[i].angle+(j+1)*pi/2);
swap(a,b);
}
graham();
printf("%.2lf\n",ans);
return 0;
}
