hdoj 1348 Wall (凸包周长)

本文主要是介绍hdoj 1348 Wall (凸包周长)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=1348
题意：一个国王有 $n$ 个城堡，他要在这些城堡外建城墙，使得城墙距离任一城堡的距离都大于 $l$ ，给出这些城堡的坐标，求城墙的最小周长。

找到这些城堡的凸包，然后对于凸包的边平行着建就行，在拐角处画一个半径为 $l$ 的圆弧，最终所有圆弧合起来正好是一个半径为 $l$ 的圆，所以最终答案是凸包的周长+半径为 l <script type="math/tex" id="MathJax-Element-400">l</script> 的圆的周长。
求凸包用的是Graham算法，最后结果要四舍五入。
还有一个小小的格式问题就是每组数据之间有一个空行，最后一组数据后面没有空行。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
struct node
{int x,y;
} a[105],p[105];
int top,n;
double l,ans,pi=acos(-1.0);
double cross(node p0,node p1,node p2)//计算叉乘，p0p1 X p0p2 注意p0,p1,p2的位置，这个决定了方向
{return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
}
double dis(node a,node b)//计算距离，这个用在了当两个点在一条直线上
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(node p1,node p2)//极角排序
{double z=cross(a[0],p1,p2);if(z>0||(z==0&&dis(a[0],p1)<dis(a[0],p2)))return 1;return 0;
}
int round_double(double number)
{return (number>0.0)?(number+0.5):(number-0.5);
}
void Graham()
{int k=0;for(int i=0; i<n; i++)if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))k=i;swap(a[0],a[k]);//找p[0]，取最下，同最下取最左sort(a+1,a+n,cmp);top=1;p[0]=a[0];p[1]=a[1];for(int i=2; i<n; i++)//控制进栈出栈{while(cross(p[top-1],p[top],a[i])<0&&top)top--;top++;p[top]=a[i];}
}
int main()
{int T;scanf("%d",&T);while(T--){ans=0;scanf("%d%lf",&n,&l);for(int i=0; i<n; i++){scanf("%d%d",&a[i].x,&a[i].y);}Graham();top++;p[top]=p[0];for(int i=0;i<top;i++){ans+=dis(p[i],p[i+1]);}printf("%d\n",round_double(ans+l*2*pi));if(T) printf("\n");}return 0;
}