这道题是水题,发现平移某些边,答案就是圆心的凸包+一个圆的周长。
不要忽视精度误差!
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=;
const double eps=1e-;
const double Pi=acos(-1.0);
int sgn(double x){
if(x>eps)return ;
if(x<-eps)return -;
return ;
}
struct Point{
double x,y;
Point(double _=,double __=){x=_;y=__;}
friend Point operator+(Point a,Point b){
return Point(a.x+b.x,a.y+b.y);
}
friend Point operator-(Point a,Point b){
return Point(a.x-b.x,a.y-b.y);
}
friend bool operator<(Point a,Point b){
return sgn(a.y-b.y)?sgn(b.y-a.y)>:sgn(b.x-a.x)>;
}
}st[*N],p[*N];
double Cross(Point a,Point b){
return a.x*b.y-a.y*b.x;
} Point Rotate(Point a,double th){
double s=sin(th),c=cos(th);
return Point(a.x*c-a.y*s,a.x*s+a.y*c);
} double sqr(double x){return x*x;}
double Dis(Point a,Point b){
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
} bool cmp(Point a,Point b){
double c=Cross(a-p[],b-p[]);
if(sgn(c)>)return true;
if(sgn(c)<)return false;
return sgn(Dis(p[],b)-Dis(p[],a))>;
} double a,b,r;
double x,y,th;
int n,pos,top,tot;
int main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
scanf("%d",&n);
scanf("%lf%lf%lf",&b,&a,&r);
a=a/2.0;a=a-r;b=b/2.0;b=b-r;
for(int i=;i<=n;i++){
scanf("%lf%lf%lf",&x,&y,&th);
Point O(x,y);
p[i*-]=Rotate(Point(x+a,y+b)-O,th)+O;
p[i*-]=Rotate(Point(x+a,y-b)-O,th)+O;
p[i*-]=Rotate(Point(x-a,y+b)-O,th)+O;
p[i*-]=Rotate(Point(x-a,y-b)-O,th)+O;
}
sort(p,p+*n);
for(int i=;i<*n;i++){
if(i==)p[tot++]=p[i];
else if(sgn(p[i].x-p[i-].x)||sgn(p[i].y-p[i-].y))
p[tot++]=p[i];
}
sort(p+,p+tot,cmp);p[tot]=p[];
st[]=p[];st[]=p[];top=;
for(int i=;i<=tot;i++){
while(top>=&&sgn(Cross(st[top]-p[i],st[top-]-p[i]))>=)top--;
st[++top]=p[i];
}
double ans=2.0*Pi*r;
for(int i=;i<=top;i++)
ans+=Dis(st[i],st[i-]);
printf("%.2f\n",ans);
return ;
}