A - Wall
POJ - 1113题意：给一些点求一个墙把所有点都包围并且墙到点的距离至少为L所以求出凸包来之后在加上一个 以L为半径的圆的周长即可。那个墙的图形就是把凸包的边向外平移L然后它们之间就不连接了所有需要加上一段圆弧而最小呢就是以每个定点为圆心L为半径的圆弧由外角和得出360恰好所有圆弧构成一个以L为半径的圆 #include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 1005
const double pai=acos(-1.0);
struct node
{
double x,y;
} p[maxn];
double l,ans;
int n,stk[maxn],top;
int cha(node p0,node p1,node p2)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(node p0,node p1)
{
return sqrt((p1.x-p0.x)*(p1.x-p0.x)+(p1.y-p0.y)*(p1.y-p0.y));
}
bool cmp(node p0,node p1)
{
int temp = cha(p[1],p0,p1);
if(temp>0)
return true;
else if(temp==0&&(dis(p[1],p0)<dis(p[1],p1)))return true;
return false;
}
int main()
{
scanf("%d%lf",&n,&l);
for(int i=1; i<=n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
if(p[i].x<p[1].x||((p[i].x==p[1].x)&&(p[i].y<p[1].y)))
swap(p[i],p[1]);
}
sort(p+2,p+1+n,cmp);
ans=l*2*pai;
stk[++top]=1;
for(int i=2; i<=n; i++)
{
while(top>1&&cha(p[stk[top-1]],p[stk[top]],p[i])<=0)top--;
stk[++top]=i;
}
ans+=dis(p[stk[1]],p[stk[top]]);
for(int i=1; i<top; i++)
ans+=dis(p[stk[i]],p[stk[i+1]]);
printf("%d\n",(int)(ans+0.5));
return 0;
}
