凸包裸题
解法
结论
答案是凸包长度和一个直径是 $L$ 的圆周长的和，如图。
黑色实线即为答案所求的轮廓的长度。
因为题中要求轮廓到所有点的距离大于等于 $L$，显然我们要控制所有凸包上的点到轮廓的距离等于 $L$。我们自然想到了如图的方法，把凸包平移出去 $L$ 的长度，在有点的地方，轮廓即为一段圆弧。因为凸包多凸多边形，而凸多边形的外角和为 $360^{\circ}$，所以所有圆弧长度和等于一个直径为 $L$ 的圆的周长。
为什么要选凸包
如果不选凸包而选一个凹进去的形状，如图，显然答案的折现比凹进去的点 $Q,O,T,U,R$ 连成的线更优。
代码
#include<bits/stdc++.h>
int t,n,beginning,L;
double ans,pi=acos(-1),bx,by;
struct point
{
double x,y,deg;
point()
{
x=0x3f3f3f3f,y=0x3f3f3f3f;
}
point(int x,int y)
{
this->x=x,this->y=y;
}
inline void calc()
{
if(x==0)
{
if(y==0) deg=0;
else deg=90;
}else deg=atan2(y,x)*180/pi;
}
inline friend double distance(const point &lhs,const point &rhs)
{
return sqrt((lhs.x-rhs.x)*(lhs.x-rhs.x)+(lhs.y-rhs.y)*(lhs.y-rhs.y));
}
inline bool operator<(const point &rhs) const
{
if(deg==rhs.deg) return distance((point){0,0},*this)<distance((point){0,0},rhs);
return deg<rhs.deg;
}
};
point a[10010];
std::vector<point> v;
inline int min(const int &lhs,const int &rhs)
{
if(a[lhs].y==a[rhs].y) return a[lhs].x<a[rhs].x?lhs:rhs;
return a[lhs].y<a[rhs].y?lhs:rhs;
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&L),beginning=0,v.clear();
for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y),beginning=min(beginning,i);
bx=a[beginning].x,by=a[beginning].y;
for(int i=1;i<=n;i++) a[i].x-=bx,a[i].y-=by,a[i].calc();
std::swap(a[1],a[beginning]),std::sort(a+2,a+n+1),a[++n]=a[1],v.push_back(a[1]),v.push_back(a[2]);
ans=distance(v[0],v[1]);
for(int i=3;i<=n;i++)
{
while(1)
{
if((a[i].x-v[v.size()-2].x)*(v.back().y-v[v.size()-2].y)>(v.back().x-v[v.size()-2].x)*(a[i].y-v[v.size()-2].y))
ans-=distance(v.back(),v[v.size()-2]),v.pop_back();
else break;
}
v.push_back(a[i]),ans+=distance(v.back(),v[v.size()-2]);
}
printf("%.0lf\n",ans+pi*L*2);
if(t) printf("\n");
}
return 0;
}
