Description

农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

Input

输入数据的第一行包括一个整数 N。N（0 <= N <= 10,000）表示农夫约翰想要围住的放牧点的数目。接下来N 行，每行由两个实数组成，Xi 和 Yi,对应平面上的放牧点坐标（-1,000,000 <= Xi,Yi <= 1,000,000）。数字用小数表示。

Output

输出必须包括一个实数，表示必须的围栏的长度。答案保留两位小数。

Sample Input

44 84 125 9.37 8

Sample Output

12.00

Source

USACO


题意：给你n个点，让你用栅栏把这n个点圈起来，问圈住n个点的最小长度。

就是要求你求维护一个凸包，光荣的成为了一道凸包的裸题。

我才不会告诉你这是我第一个不看任何模板自己写出的算法呢。

我求凸包用的是卷包裹法。

卷包裹法：http://blog.csdn.net/lzr010506/article/details/50775301

代码：

#include <bits/stdc++.h>
using namespace std;
struct Point
{
	double x, y;
}a[10010];
int n, P, b[10010], tb[10010];

inline double sq(double x)
{
	return x * x;
}

inline double cj(Point a, Point b, Point c)//求向量 a->b a->c 的叉积 
{
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
//b.x-a.x b.y-a.y  c.x-a.x c.y-a.y 
inline double dis(Point a, Point b)
{
	return sqrt( sq(b.x - a.x) + sq(b.y - a.y) );
}

int main()
{
	scanf("%d",&n);
	double px = 1000010.0, py = 1000010.0;
	for(int i = 1; i <= n; i ++)
	{
		scanf("%lf%lf",&a[i].x, &a[i].y);
		if(px > a[i].x) P = i, px = a[i].x, py = a[i].y;
		else 
			if(px == a[i].x) 
				if(py > a[i].y) P = i, py = a[i].y;
	}
	if(n == 1) 
	{
		printf("0.00");
		return 0;
	}
	if(n == 2)
	{
		printf("%.2lf",dis(a[1], a[2]));
		return 0;
	}
	
	int cnt = 1;
	Point now;
	now = a[P];
	tb[cnt] = P;
	while(now.x != a[P].x || now.y != a[P].y || cnt == 1) 
	{
		Point p;
		int pp;
		for(int i = 1; i <= n; i ++)
			if(b[i] == 0)
			{
				p = a[i];
				pp = i;
				break;
			}
		for(int i = 1; i <= n; i ++)
		{
			if(b[i] == 1) continue;
			double now_cj = cj(now, p, a[i]);
			if(now_cj == 0) 
			{
				double dp = dis(now, p);
				double da = dis(now, a[i]);
				if(da > dp) p = a[i],pp = i;
				continue; 
			}
			if(now_cj < 0)
				p = a[i],pp = i;
		}
		tb[++ cnt] = pp;
		now = p;
		b[pp] = 1;
	}
	double ans = 0.00;
	for(int i = 2; i <= cnt; i ++)
		ans += dis( a[tb[i]], a[tb[i - 1]] );
	printf("%.2lf", ans);
	return 0;
}