这道题有点复杂,思考了很久
其实本质上就是求以所有信用卡的圆心为点集,求这个点集的凸包的周长
最后再求长度为$r$的圆的周长
有一个结论是:最终凸包的圆弧总长恰好等于一个给定半径为 $r$ 的圆的周长。
证明略了,有兴趣的自己证明一下,或者百度
代码如下
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
typedef long long ll;
const double eps=1e-8;
const double pi=acos(-1);
double a,b,r;
int sgn(double x)
{
if (fabs(x)<eps) return 0;
return x<0?-1:1;
}
struct Point
{
double x,y;
Point (){}
Point (double x,double y):x(x),y(y){}
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 operator *(double k){return Point(x*k,y*k);}
Point operator /(double k){return Point(x/k,y/k);}
//下面两个是用于构造凸包前的排序
bool operator ==(Point B){return sgn(x-B.x)==0&&sgn(y-B.y)==0;}
bool operator < (Point B){return sgn(x-B.x)<0||sgn(x-B.x)==0&&sgn(y-B.y)<0;}
};
//旋转
Point Rotate(Point A,double rad){return Point(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
const int N=1e5+100;
Point p[N],hull[N];
double Cross(Point A,Point B){return A.x*B.y-A.y*B.x;}
int Convex_hull(Point *p,int n,Point *ch)
{
sort(p,p+n);
n=unique(p,p+n)-p;
int v=0;
for(int i=0;i<n;i++)
{
while(v>1&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)
v--;
ch[v++]=p[i];
}
int j=v;
for(int i=n-2;i>=0;i--)
{
while(v>j&&sgn(Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]))<=0)
v--;
ch[v++]=p[i];
}
if (n>1) v--;
return v;
}
double Distance(Point A,Point B){return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));}
int main(){
int n,cnt=0;;
scanf("%d",&n);
scanf("%lf%lf%lf",&a,&b,&r);
a=a/2-r,b=b/2-r;//这个地方是一个坑,我们要求得凸包顶点是四个角的圆心,卡了很久
for(int i=0;i<n;i++)
{
Point u;
double ang;
scanf("%lf%lf%lf",&u.x,&u.y,&ang);
//旋转法,求四个顶点,不会证明可以去看oiwiki里的向量旋转
p[cnt++]=Rotate(Point(-b,a),ang)+u;
p[cnt++]=Rotate(Point(-b,-a),ang)+u;
p[cnt++]=Rotate(Point(b,-a),ang)+u;
p[cnt++]=Rotate(Point(b,a),ang)+u;
}
int num=Convex_hull(p,cnt,hull);
double res=0;
for(int i=0;i<num;i++) res+=Distance(hull[i],hull[(i+1)%num]);
//cout<<num<<endl;
//for(int i=0;i<num;i++) cout<<hull[i].x<<' '<<hull[i].y<<endl;
res+=2*pi*r;
printf("%.2f",res);
return 0;
}