题目描述
输入
输出
样例输入
2
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
6.0 2.0 0.0
0.0 0.0 0.0
2.0 -2.0 1.5707963268
样例输出
21.66
提示
本样例中的2张信用卡的轮廓在上图中用实线标出，如果视1.5707963268为
Pi/2(pi为圆周率),则其凸包的周长为16+4*sqrt(2)
我们先将每个信用卡看成是由四个圆心组成的矩形，那么凸包就是所有圆心形成的凸包。现在每个圆心往外扩展为一个圆，那么就是用凸包来包住所有的圆，而新的凸包的直边部分就是原凸包对应边往外平移得到。对于曲面部分，因为一个凸多边形外角和为360度，所以曲面部分就是一个圆的周长。直接求所有圆心形成凸包的周长再加上一个圆的周长即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double pi=acos(-1.0);
struct lty
{
double x,y;
lty(double X=0,double Y=0){x=X,y=Y;}
}a[40010];
lty operator -(lty a,lty b){return lty(a.x-b.x,a.y-b.y);}
double operator *(lty a,lty b){return a.x*b.y-b.x*a.y;}
int st[40010];
int vis[40010];
int top;
int n;
int cnt;
double x,y,r;
double X,Y,R;
double ans;
lty res;
bool cmp(lty a,lty b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
int main()
{
scanf("%d",&n);
scanf("%lf%lf%lf",&X,&Y,&R);
X=X/2-R,Y=Y/2-R;
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&x,&y,&r);
a[++cnt]=lty(x+Y*cos(r)+X*sin(r),y+Y*sin(r)-X*cos(r));
a[++cnt]=lty(x-Y*cos(r)+X*sin(r),y-Y*sin(r)-X*cos(r));
a[++cnt]=lty(x+Y*cos(r)-X*sin(r),y+Y*sin(r)+X*cos(r));
a[++cnt]=lty(x-Y*cos(r)-X*sin(r),y-Y*sin(r)+X*cos(r));
}
sort(a+1,a+1+cnt,cmp);
st[++top]=1;
for(int i=2;i<=cnt;i++)
{
while(top>1&&(a[st[top]]-a[st[top-1]])*(a[i]-a[st[top]])<=0)
{
vis[st[top--]]=0;
}
vis[i]=1;
st[++top]=i;
}
int lim=top;
for(int i=cnt-1;i>=1;i--)
{
if(!vis[i])
{
while(top>lim&&(a[st[top]]-a[st[top-1]])*(a[i]-a[st[top]])<=0)
{
vis[st[top--]]=0;
}
vis[i]=1;
st[++top]=i;
}
}
for(int i=1;i<top;i++)
{
res=a[st[i+1]]-a[st[i]];
ans+=sqrt(res.x*res.x+res.y*res.y);
}
printf("%.2f",ans+2*pi*R);
}