麦兜是个淘气的孩子。一天，他在玩钢笔的时候把墨水洒在了白色的墙上。再过一会，麦兜妈就要回来了，麦兜为了不让妈妈知道这件事情，就想用一个白色的凸多边形把墙上的墨点盖住。你能告诉麦兜最小需要面积多大的凸多边形才能把这些墨点盖住吗？
现在，给出了这些墨点的坐标，请帮助麦兜计算出覆盖这些墨点的最小凸多边形的面积。
现在，给出了这些墨点的坐标，请帮助麦兜计算出覆盖这些墨点的最小凸多边形的面积。
Description
多组测试数据。第一行是一个整数T，表明一共有T组测试数据。
每组测试数据的第一行是一个正整数N(0< N < = 105)，表明了墨点的数量。接下来的N行每行包含了两个整数Xi和Yi（0<=Xi,Yi<=2000），表示每个墨点的坐标。每行的坐标间可能包含多个空格。
每组测试数据的第一行是一个正整数N(0< N < = 105)，表明了墨点的数量。接下来的N行每行包含了两个整数Xi和Yi（0<=Xi,Yi<=2000），表示每个墨点的坐标。每行的坐标间可能包含多个空格。
Input
每行输出一组测试数据的结果，只需输出最小凸多边形的面积。面积是个实数，小数点后面保留一位即可，不需要多余的空格。
Output
|
1
2
3
4
5
6
7
8
9
|
2
4
0 0
1 0
0 1
1 1
2
0 0
0 1
|
Sample Input
|
1
2
|
1.0
0.0
|
Sample Output
Hint
就是一个凸包的点集覆盖求最小覆盖面积~~~
一个告诉多边形顶点坐标的面积求法（按顺序给出）
area += (pos.x*tmp.y - pos.y*tmp.x) / 2.0;(pos当前点，tmp下一个点，最后一个点和第一个点在来一次)
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<stack> 5 #include<cmath> 6 using namespace std; 7 struct node{ 8 double x, y; 9 }point[110], pos, tmp; 10 double dis(node a, node b){ 11 return pow((a.x - b.y), 2) + pow((a.y - b.y), 2); 12 } 13 //按点集分布排序,利用向量平行关系判断(极角排序)，角度相同则距离小的在前面 14 bool cmp(node a, node b){ 15 double povit = (a.x - pos.x)*(b.y - pos.y) - (b.x - pos.x)*(a.y - pos.y); 16 if (povit > 0 || !povit && (dis(a, pos) < dis(b, pos))) 17 return true; 18 return false; 19 } 20 //当前点是否在点集左侧,利用叉乘比较3个点两条线的斜率关系 21 bool turn_left(node p1, node p2, node p3){ 22 return (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y - p3.x*p1.y - p1.x*p2.y - p2.x*p3.y) > 0 ? true : false; 23 } 24 int main(){ 25 int i, sign, n, t; 26 double area; 27 cin >> t; 28 while (t--){ 29 cin >> n; 30 for (i = 0; i < n; i++) 31 cin >> point[i].x >> point[i].y; 32 if (n <= 2){ 33 cout << "0.0 "; 34 continue; 35 } 36 stack<node> Q; 37 sign = 0; 38 pos = point[0]; 39 for (i = 1; i < n; i++){ 40 if (pos.y == point[i].y&&pos.x>point[i].x || point[i].y < pos.y){ 41 pos = point[i]; 42 sign = i; 43 } 44 } 45 swap(point[0], point[sign]); 46 sort(point + 1, point + n, cmp); 47 Q.push(point[0]), Q.push(point[1]), Q.push(point[2]); 48 for (i = 3; i < n; i++){ 49 while (!Q.empty()){ 50 tmp = Q.top(); 51 Q.pop(); 52 if (turn_left(tmp, Q.top(), point[i])){ 53 Q.push(tmp); 54 break; 55 } 56 } 57 Q.push(point[i]); 58 } 59 area = 0; 60 tmp = Q.top(), Q.pop(); 61 area += (pos.x*tmp.y - pos.y*tmp.x) / 2.0; 62 while (!Q.empty()){ 63 area += (tmp.x*Q.top().y - tmp.y*Q.top().x) / 2.0; 64 tmp = Q.top(); 65 Q.pop(); 66 } 67 printf("%.1lf ", fabs(area)); 68 } 69 return 0; 70 }
主要的地方就是利用向量平行关系，按点集的离散化排序
（没说清楚~~~看凸包的简单概念吧http://www.cnblogs.com/zyxStar/p/4540984.html）,
判断下一个的点能否覆盖已选取的点~~