Cows
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 6245 Accepted: 2850
Description
Your friend to the south is interested in building fences and turning plowshares into swords. In order to help with his overseas adventure, they are forced to save money on buying fence posts by using trees as fence posts wherever possible. Given the locations of some trees, you are to help farmers try to create the largest pasture that is possible. Not all the trees will need to be used.
However, because you will oversee the construction of the pasture yourself, all the farmers want to know is how many cows they can put in the pasture. It is well known that a cow needs at least 50 square metres of pasture to survive.
Input
The first line of input contains a single integer, n (1 ≤ n ≤ 10000), containing the number of trees that grow on the available land. The next n lines contain the integer coordinates of each tree given as two integers x and y separated by one space (where -1000 ≤ x, y ≤ 1000). The integer coordinates correlate exactly to distance in metres (e.g., the distance between coordinate (10; 11) and (11; 11) is one metre).
Output
You are to output a single integer value, the number of cows that can survive on the largest field you can construct using the available trees.
Sample Input
4
0 0
0 101
75 0
75 101
Sample Output
151
這道題，計算幾何，恩，求凸包的面積。
題意就是，這個人要在森林中把幾棵樹圍起來養牛，一只牛占地50，
給你一些樹的坐標問，最多養多少頭牛。
就是，求凸包面積，然後除以50.。。。
這道題有一點，那個面積用整型存儲，浮點類型存儲會WA。。。
代碼，就是貼求凸包的模板（Graham算法）
然後，根據凸包數組，求一個個三角形面積。
三角形面積，就是叉積的一半，叉積求的是平行四邊形面積。
/*
Author：Tree
From： http://blog.csdn.net/lttree
Cows
poj 3348
凸包面積
*/
#include
#include
#include
using namespace std;
struct point
{
double x,y;
}pnt[10001],res[10001];
// 兩向量叉積
double cross( point sp,point ep,point op)
{
return (sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y);
}
// sort數組排序，比較的<號重載
bool operator < (const point &l,const point &r)
{
return l.y=0 ) top--;
res[++top] = pnt[i];
}
len = top; res[++top] = pnt[n-2];
// 判斷最後三個點
for(i=n-3;i>=0;--i)
{
while( top!=len && cross(pnt[i],res[top],res[top-1])>=0 ) top--;
res[++top] = pnt[i];
}
return top;
}
int main()
{
int n,i,len;
int area;
while(scanf(%d,&n)!=EOF && n)
{
for(i=0;i
