【POJ1113】Wall-Graham-Scan算法求凸包

测试地址：Wall

题目大意：一个国王有n个城堡（可以看做平面上的点），现在要建一堵封闭的城墙将所有城堡围住，并且使得城墙与每座城堡的最短距离不超过L，求满足条件的最短城墙长度。

做法：可以证明，最短城墙长度等于这n个点的凸包周长加上一个半径为L的圆的周长，所以问题就转变为求这n个点的凸包，这里用基于极角排序的Graham-Scan算法来求凸包，时间复杂度为O(nlogn)。输出要注意，如果选C++就是%.0lf，如果选G++就是%.0f，否则会WA，我也不知道为什么......

以下是本人代码：

#include <cstdio>#include <cstdlib>#include <iostream>#include <algorithm>#include <cmath>#define pi 3.14159265#define e 0.00000001using namespace std;int n,s[1010],top=1;double l,ans=0;struct point{  double x,y;  point Operator - (point b)  {    point s;	s.x=x-b.x;	s.y=y-b.y;	return s;  }}p[1010];double multi(point a,point b){  return a.x*b.y-b.x*a.y;}double dist(point a,point b){  return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}bool cmp(point a,point b){  if (a.x!=b.x) return a.x<b.x;  return a.y<b.y;}bool cmp2(point a,point b){  double m=multi(a-p[1],b-p[1]);  if (fabs(m)<=e) return dist(a,p[1])<dist(b,p[1]);  return m>0;}void graham(){  top=2,s[1]=1,s[2]=2;  for(int i=3;i<=n;i++)  {    while(top>1&&multi(p[s[top]]-p[s[top-1]],p[i]-p[s[top]])<=0) top--;	s[++top]=i;  }}int main(){  scanf("%d%lf",&n,&l);  for(int i=1;i<=n;i++)    scanf("%lf%lf",&p[i].x,&p[i].y);    sort(p+1,p+n+1,cmp);  sort(p+2,p+n+1,cmp2);  graham();    for(int i=1;i<top;i++)    ans+=dist(p[s[i]],p[s[i+1]]);  ans+=dist(p[1],p[s[top]]);  ans+=pi*2*l;    PRintf("%.0f",ans);    return 0;}