UVa 1303 - Wall

題目：有非常多點。修一座最短的圍牆把素有點圍起來，使得全部點到牆的距離不小于l。

分析：計算幾何，凸包。

            假設。沒有距離l的限制。則答案就是凸包的周長了。有了距離限制事實上是添加了2*π*l。

            證明：如上圖。在凸包外做相應邊的矩形；

                        多邊形内角和 = 180*（n-2）；

                        外角和 = 360*n - 内角和 = 180*n+360；

                        全部直角和為2*90*n；

                        是以，全部扇形的内角和為360；即圍欄比凸多邊形周長多2*π*l。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>

using namespace std;

typedef struct pnode
{
	int  x,y;
	double d;
}point;
point P[1005];

//叉乘 
int crossProduct(point a, point b, point c)
{
	return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-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)+0.0);
}

//坐标比較 
int cmp1(point a, point b)
{
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

//斜率比較 
int cmp2(point a, point b)
{
	int cp = crossProduct(P[0], a, b);
	if (!cp) return a.d < b.d;
	return cp > 0;
}

//凸包 
double Graham(int n)
{
	sort(P+0, P+n, cmp1);
	for (int i = 1 ; i < n ; ++ i)
		P[i].d = dist(P[0], P[i]);
	sort(P+1, P+n, cmp2);
	
	int top = 1;
	for (int i = 2 ; i < n ; ++ i) {
		while (top > 0 && crossProduct( P[top-1], P[top], P[i] ) < 0) -- top;
		P[++ top] = P[i];
	}
	P[++ top] = P[0];
	
	double L = 0.0;
	for ( int i = 0 ; i < top ; ++ i )
		L += dist(P[i], P[i+1]);
	return L;
}

int main()
{
	int t,n,l;
	while (~scanf("%d",&t))	
	while (t --) {
		scanf("%d%d",&n,&l);
		for (int i = 0 ; i < n ; ++ i)
			scanf("%d%d",&P[i].x,&P[i].y);
		
		printf("%.0lf\n",Graham(n)+acos(-1.0)*2*l);
		if (t) printf("\n");
	}
	return 0;
}