二维凸包

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

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

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

输入输出样例
输入 #1复制
4
4 8
4 12
5 9.3
7 8
输出 #1复制
12.00

比较明显的求二维凸包的周长，面积也是一样的，算算三角形面积即可。

通常求二维凸包，用Graham扫描法，按照极角排序之后，利用叉积判断当前点是否可以属于凸包。就是利用叉积顺时针为负，逆时针为正。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e4+10;
const double eps=1e-7;
int top,n;
double res;
struct node{double x,y,c;}t[N],st[N];
int cmp(node a,node b){
	double a1=atan2(a.y-t[1].y,a.x-t[1].x),a2=atan2(b.y-t[1].y,b.x-t[1].x);
	return a1==a2?a.x<b.x:a1<a2;
}
inline double dis(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double corss(node a,node b,node c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
void Graham(){
	int id=1;
	for(int i=2;i<=n;i++)	
		if(t[id].y>t[i].y||(t[id].y==t[i].y&&t[id].x>t[i].x))	id=i;
	swap(t[1],t[id]);	sort(t+2,t+1+n,cmp);	st[++top]=t[1];
	for(int i=2;i<=n;i++){
		while(top>=2&&corss(st[top-1],t[i],st[top])>=0)	top--;
		st[++top]=t[i];
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%lf %lf",&t[i].x,&t[i].y);
	Graham(); res=dis(st[1],st[top]);
	for(int i=2;i<=top;i++)	res+=dis(st[i],st[i-1]);
	printf("%.2lf\n",res);
	return 0;
}