凸包面积

Sample Input

240 01 00 11 120 00 1

Sample Output

1.00.0

这个算法可以这样表示：1.  将各点排序（必须的） ，为保证形成圈，把 P0 在次放在点表的尾部；2.  准备堆栈：建立堆栈 S，栈指针设为t，将0、1、2 三个点压入堆栈 S；3.  对于下一个点 i    只要 S[t-1]、S[t]、i不做左转      就反复退栈；    将 i压入堆栈 S4.堆栈中的点即为所求凸包；   其核心用 C 语言表示，仅仅是下面一段：     t=-1;      s[++t]=0; s[++t]=1; s[++t]=2;      for (i=3;i<n;i++)     {          while (!left(s[t-1],s[t],i))             t--;          s[++t]=i;     }下面我们来看一个例子：这是排序后的几个点

准备堆栈（有线段相连的点表示在栈中的点）
栈内元素：P0,P1,P2

考虑 P3：P1,P2,P3呈左转，P3入栈
栈内元素：P0,P1,P2,P3

考虑 P4：P2,P3,P4呈左转，P4入栈
栈内元素：P0,P1,P2,P3,P4

考虑 P5：P3,P4,P5非左转，退栈
栈内元素：P0,P1,P2,P38

现在，P2,P3,P5 呈左转，P5入栈
栈内元素：P0,P1,P2,P3,P5

（此时情况如图，算法舍弃了 P4）

以此方法进行下去，直到所有点都被考虑过
最终的栈中元素为 P0,P1,P2,P3,P8,P0，正是所求凸包
擦去其他点后，如图所示：

   如果给定点集有 n个点，则此过程的算法复杂度为 O(n)，加上排序的过程，
整个算法复杂度是 O(nlogn)

C++代码

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <stack>
  4 #include <iomanip>
  5 #define max 106 
  6 using namespace std;
  7 
  8 struct point
  9 {
 10     int x, y;
 11 };
 12 
 13 point spot[max], p0;
 14 //p1p2距离
 15 int dis(const point &p1, const point &p2)
 16 {
 17     return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
 18 }
 19 //p1在p1p2左侧
 20 bool compares(const point &p1, const point &p2)
 21 {
 22     int t;
 23     t = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
 24     if(t > 0 || (t == 0 && dis(p1, p0) < dis(p2, p0)))
 25         return true;
 26     else
 27         return false;
 28 }
 29 double area(point p1,point p2,point p3)  //计算三角形面积；
 30 {
 31     double s;
 32     s=(p1.x*(p2.y-p3.y)+p2.x*(p3.y-p1.y)+p3.x*(p1.y-p2.y))/2.0;
 33     return s;
 34 }
 35 int main()
 36 {
 37     int n, i, x, y, p,m;
 38     stack<point> s;
 39     cin>>m;
 40     while(m--)
 41     {
 42         cin>>n;
 43         for(i = 0; i < n; i++)
 44             cin>>spot[i].x>>spot[i].y;
 45         x = spot[0].x;
 46         y = spot[0].y;
 47         p = 0;
 48         for(i = 1; i < n; i++)      //寻找最左上的点
 49         {
 50             if((spot[i].y == y && spot[i].x < x)||spot[i].y < y)
 51             {
 52                 x = spot[i].x;
 53                 y = spot[i].y;
 54                 p = i;
 55             }
 56         }
 57         //x,y为最做点，即p0确定
 58         p0.x = x;
 59         p0.y = y;
 60         
 61         swap(spot[0], spot[p]);
 62         sort(spot + 1, spot + n, compares);        
 63         //将0、1、2 三个点压入堆栈 S
 64         s.push(p0);
 65         s.push(spot[1]);
 66         s.push(spot[2]);
 67         
 68         point temp;
 69         for(i = 3; i < n; i++)       //凸包
 70         {
 71             while(!s.empty())
 72             {
 73                 temp = s.top(); 
 74                 s.pop();
 75                 p = (s.top().x)*temp.y+spot[i].x*(s.top().y)+temp.x*(spot[i].y)-spot[i].x*(temp.y)-temp.x*(s.top().y)-s.top().x*(spot[i].y);
 76                 if(p>0)//i位于spot[t-1]spot[t]左侧
 77                 {
 78                     s.push(temp); //将temp重新压入栈中
 79                     break;
 80                 }
 81             }
 82             s.push(spot[i]); //将i 压入栈中
 83         }
 84         
 85         double area = 0;
 86         temp = s.top();
 87         s.pop();
 88         area += (p0.x * temp.y - p0.y * temp.x)/2.0;
 89         while(!s.empty())
 90         {
 91             area += (temp.x * s.top().y - temp.y * s.top().x)/2.0;
 92             temp = s.top();
 93             s.pop();
 94         }
 95         if (n<=2)
 96         {
 97             area =0;
 98         }
 99         if(area < 0)
100         {
101             area = -area;
102         }    
103         cout<<setiosflags(ios::fixed)<<setprecision(1)<<area<<endl;
104     }
105 
106     return 0;
107 }