UVa 1303 - Wall

题目：有非常多点。修一座最短的围墙把素有点围起来，使得全部点到墙的距离不小于l。

分析：计算几何，凸包。

假设。没有距离l的限制。则答案就是凸包的周长了。有了距离限制事实上是添加了2*π*l。

证明：如上图。在凸包外做相应边的矩形；

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

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

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

所以，全部扇形的内角和为360；即围栏比凸多边形周长多2*π*l。

说明：坐标比較a3.x < b.x 写成 a.x < b.y 查了好久才发现。o(╯□╰)o

#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;

}