C时间限制：3000 毫秒 | C内存限制：3000 Kb
题目内容：
在一片草地上长着一些分散的树，现在要在这片草地上建造一个牧场，方法是将草地上的树看成平面上的点，在这些点找到可以围成的最大凸多边形，用绳子将凸多边形圈起来即可，已知牧场上每50平方米可以养一头奶牛，则所围成的牧场最多可以养多少头奶牛？
输入描述
多组输入！
第一行输入包含一个整数n（1≤n≤10000），包含在可用土地上生长的树的数量。 接下来的n行包含每个树的整数坐标，以两个整数x和y分隔一个空格（其中-1000≤x，y≤1000）。 整数坐标精确地与以米为单位的距离相关（例如，坐标（10; 11）和（11; 11）之间的距离是一米）。
输出描述
您将输出一个整数值，即可以使用可用树构建的最大牧场上可以存活的奶牛数量。
输入样例
4 0 0 0 101 75 0 75 101
输出样例
151
思路：凸包裸题，熟悉下凸包的使用
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 10005
int n,tot;//n为二维平面上点的个数，tot为凸包上点的个数
struct node {
int x,y;
}a[N],p[N]; //p[]用来储存凸包
double dis(node a1,node b1){ //两点间距离公式
return (a1.x-b1.x)*(a1.x-b1.x)+(a1.y-b1.y)*(a1.y-b1.y);
}
//叉积：返回结果为正说明p2在向量p0p1的左边（三点构成逆时针方向）；
//为负则相反；为0则三点共线(叉积的性质很重要)
double multi(node p0,node p1,node p2){ //
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//极角排序：极角排序是根据坐标系内每一个点与x轴所成的角，逆时针比较。按照角度从小到大的方式排序
int cmp(node p1,node p2){ //极角排序；
int x=multi(p1,p2,a[0]);
if(x>0||(x==0&&dis(p1,a[0])<dis(p2,a[0])))
return 1;
return 0;
}
void Graham(){ //求凸包
int k=0;
for(int i=0;i<n;i++) //找到最下最左的一个点
if(a[i].y<a[k].y||(a[i].y==a[k].y&&a[i].x<a[k].x))
k=i;
swap(a[0],a[k]); //将其设置为第一个点
sort(a+1,a+n,cmp);
tot=2,p[0]=a[0],p[1]=a[1]; //p[]模拟栈，用来储存凸包
for(int i=2;i<n;i++){
while(tot>1&&multi(p[tot-1],p[tot-2],a[i])>=0)
tot--; //右拐就回退
p[tot++]=a[i]; //左拐就放入
}
}
double getArea(){
struct node b[3];
b[0] = p[0], b[1] = p[1], b[2] = p[2];
double area = 0;
for(int i = 2; i < tot; i++){
area += multi(b[0], b[1], p[i]) / 2.0;
b[1] = p[i];
}
return area;
}
int main(){
while(cin >> n){
tot = 0;
for(int i = 0; i < n; i++){
cin >> a[i].x >> a[i].y;
}
Graham();
double area = getArea();
cout << (int)(area / 50.0) << endl;
}
return 0;
}