题目大意：
给定一些点，求这些点围成的最大面积。。又每头牛占地50，求最大能养牛数。。
思路：
凸包，然后叉积求面积。。
code：
1 /* 2 Time:2013-04-06 13:34:19 3 State:Accepted 4 */ 5 #include<iostream> 6 #include<fstream> 7 #include<cstring> 8 #include<cstdlib> 9 #include<cstdio> 10 #include<string> 11 #include<cmath> 12 #include<algorithm> 13 struct oo{int x , y; }; 14 using namespace std; 15 int T, n, px, py , ans; 16 oo a[20000],q[20000]; 17 18 void init(){ 19 scanf("%d",&n); 20 memset(a , 0 ,sizeof(a)); 21 memset(q , 0 ,sizeof(q)); 22 for (int i = 1; i <= n ;++i) 23 scanf("%d%d",&a[i].x, &a[i].y); 24 25 } 26 27 bool cmp(const oo a , const oo b){ 28 if (a.y < b.y) return true; 29 if (a.y == b.y && a.x < b.x) return true; 30 return false; 31 32 } 33 34 bool cmpx(const oo a, const oo b){ 35 int x1 = a.x - px; 36 int x2 = b.x - px; 37 int y1 = a.y - py; 38 int y2 = b.y - py; 39 if (x1*y2-x2*y1 > 0) return true; 40 if (x1*y2 == x2*y1 && x1*x1 + y1*y1 < x2*x2 + y2*y2) return true; 41 return false; 42 } 43 void solve(){ 44 sort(a + 1, a + 1 + n, cmp); 45 px = a[1].x; 46 py = a[1].y; 47 if (n > 2) sort(a + 2, a + 1 + n, cmpx); 48 int h = 1, t = 2; 49 q[1] = a[1]; 50 q[2] = a[2]; 51 int x1, y1, x2, y2; 52 for (int i = 3; i <= n; ++i){ 53 while (true){ 54 if (t == 1) break; 55 x1 = a[i].x - q[t - 1].x; 56 x2 = q[t].x - q[t - 1].x; 57 y1 = a[i].y - q[t - 1].y; 58 y2 = q[t].y - q[t - 1].y; 59 if (x1*y2 - x2*y1 >= 0) --t; 60 else break; 61 } 62 q[++t] = a[i]; 63 } 64 ans = 0; 65 for (int i = 2; i < t; ++i){ 66 x1 = q[i].x - q[1].x; 67 y1 = q[i].y - q[1].y; 68 x2 = q[i+1].x - q[1].x; 69 y2 = q[i+1].y - q[1].y; 70 ans += abs(x1*y2 - x2*y1); 71 } 72 printf("%d\n",ans/100); 73 } 74 75 int main(){ 76 init(); 77 solve(); 78 }