关于凸包问题

Graham扫描法

基本思想：通过设置一个关于候选点的堆栈s来解决凸包问题。

操作：输入集合Q中的每一个点都被压入栈一次，非CH（Q）(表示Q的凸包)中的顶点的点最终将被弹出堆栈，当算法终止时，堆栈S中仅包含CH(Q)中的顶点，其顺序为个各顶点在边界上出现的逆时针方向排列的顺序。

注：下列过程要求|Q|>=3，它调用函数TOP（S）返回处于堆栈S 顶部的点，并调用函数NEXT-TO –TOP（S）返回处于堆栈顶部下面的那个点。但不改变堆栈的结构。

GRAHAM-SCAN(Q)

1 设P0 是Q 中Y 坐标最小的点，如果有多个这样的点则取最左边的点作为P0；

2 设<P1,P2,……,Pm>是Q 中剩余的点，对其按逆时针方向相对P0 的极角进行排序，如果有数个点有相同的极角，则去掉其余的点，只留下一个与P0 距离最远的那个点；

3 PUSH(p0 , S)

4 PUSH(p1 , S)

5 PUSH(p3 , S)

6 for i ← 3 to m

7 do while 由点NEXT-TOP-TOP（S），TOP（S）和Pi 所形成的角形成一次非左转

8 do POP(S)

9 PUSH(pi , S)

10 return S

首先，找一个凸包上的点，把这个点放到第一个点的位置P0。然后把P1~Pm 按照P0Pi的方向排序，可以用矢量积(叉积)判定。

做好了预处理后开始对堆栈中的点<p3,p4,...,pm>中的每一个点进行迭代，在第7到8行的while循环把发现不是凸包中的顶点的点从堆栈中移去。（原理：沿逆时针方向通过凸包时，在每个顶点处应该向左转。因此，while循环每次发现在一个顶点处没有向左转时，就把该顶点从堆栈中弹出。）当算法向点pi推进、在已经弹出所有非左转的顶点后，就把pi压入堆栈中。

举例如下：

　　矢量的概念：

　　如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。

　　矢量加减法：

　　设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P，P - Q = - ( Q - P )。

　　矢量叉积：

　　计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = ( x1, y1 )，Q = ( x2, y2 )，则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积，即：P × Q = x1*y2 - x2*y1，其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下，本文下述算法中所有的点都看作矢量，两点的加减法就是矢量相加减，而点的乘法则看作矢量叉积。

　　叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系：

　　若 P × Q > 0 , 则P在Q的顺时针方向。
　　若 P × Q < 0 , 则P在Q的逆时针方向。
　　若 P × Q = 0 , 则P与Q共线，但可能同向也可能反向。

　　折线段的拐向判断：

　　折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2，通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向：

　　若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

　　若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

　　若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

例题 1
问题描述1：
求覆盖平面上n 个点的最小的凸多边形。也可以这样描述：给定一个连接的多边形，可能是凸多边形，也有可能是凹多边形。现在，你的任务就是编程求这个多边形的最小凸包。如果它本身是凸多边形，那么最小凸包就是它本身。
数据范围：
多边形顶点坐标X，Y 是非负整数，不超过512。
输入：
共有K 组数据，每组测试数据的点都是按逆时针顺序输入的，没有3 个点共线。
每组测试数据的第1 行是N，表示有N 个点。以下N 行，每行两个整数X，Y。
输出：
输出格式与输入格式一样，第一行是K，表示共有K 组输出。以下K 组数据：
每组的第一行为M，表示该凸包上有M 个顶点，以下M 行每行两个整数X，Y，表示凸包顶点的坐标。也按逆时针方向输出。
样例输入：
1
14
30 30
50 60
60 20
70 45
86 39
112 60
200 113
250 50
300 200
130 240
76 150
47 76
36 40
33 35
样例输出：
1
7
60 20
250 50
300 200
130 240
76 150
47 76
30 30

  1 // In Practice, You should use the statndard input/output
  2 // in order to receive a score properly.
  3 // Do not use file input and output. Please be very careful. 
  4 
  5 #include <cstdio>
  6 #include <iostream>
  7 #include <memory.h>
  8 #include <stack>
  9 #include <vector>
 10 
 11 using namespace std;
 12 
 13 int pointNum;
 14 int lowestIndex;
 15 
 16 
 17 struct Point
 18 {
 19     int x;
 20     int y;
 21 };
 22 
 23 Point points[500];
 24 Point lowestPoint;
 25 stack<Point> pointStack;
 26 
 27 
 28 bool checkNeedToSwap(int x1, int y1, int x2, int y2)
 29 {
 30     if ((x1 - lowestPoint.x)*(y2 - lowestPoint.y) - (x2 - lowestPoint.x)*(y1 - lowestPoint.y) > 0)
 31         return true;
 32     else
 33         return false;
 34 }
 35 
 36 
 37 void sortPoints()
 38 {
 39     bool flag;
 40     int tmp[2];
 41     for (int i = 1; i < pointNum; i++)
 42     {
 43         flag = true;
 44         for (int j = pointNum - 1; j > i; j--)
 45         {
 46             if (checkNeedToSwap(points[j].x, points[j].y, points[j - 1].x, points[j - 1].y))
 47             {
 48                 tmp[0] = points[j - 1].x;
 49                 tmp[1] = points[j - 1].y;
 50                 points[j - 1].x = points[j].x;
 51                 points[j - 1].y = points[j].y;
 52                 points[j].x = tmp[0];
 53                 points[j].y = tmp[1];
 54                 flag = false;
 55             }
 56         }
 57 
 58         if (flag)
 59             break;
 60     }
 61 }
 62 
 63 
 64 void graham()
 65 {
 66     int index = 3;
 67     pointStack.push(points[0]);
 68     pointStack.push(points[1]);
 69     pointStack.push(points[2]);
 70 
 71     while (index < pointNum)
 72     {
 73         Point point2 = pointStack.top();
 74         pointStack.pop();
 75         Point point1 = pointStack.top();
 76         Point point3 = points[index];
 77 
 78         //cout << "p1(" << point1.x << " " << point1.y << ")" << endl;
 79         //cout << "p2(" << point2.x << " " << point2.y << ")" << endl;
 80         //cout << "p3(" << point3.x << " " << point3.y << ")" << endl;
 81         int tmp = (point3.x - point1.x)*(point2.y - point1.y) - (point2.x - point1.x)*(point3.y - point1.y);
 82         while (tmp > 0)
 83         {
 84             point2 = point1;
 85             pointStack.pop();
 86             point1 = pointStack.top();
 87             tmp = (point3.x - point1.x)*(point2.y - point1.y) - (point2.x - point1.x)*(point3.y - point1.y);
 88         }
 89         pointStack.push(point2);
 90         pointStack.push(point3);
 91         index++;
 92     }
 93 
 94 
 95 }
 96 
 97 
 98 
 99 
100 
101 
102 int main(int argc, char** argv)
103 {
104     int tc, T;
105 
106     // The freopen function below opens input.txt file in read only mode, and afterward,
107     // the program will read from input.txt file instead of standard(keyboard) input.
108     // To test your program, you may save input data in input.txt file,
109     // and use freopen function to read from the file when using cin function.
110     // You may remove the comment symbols(//) in the below statement and use it.
111     // Use #include<cstdio> or #include<stdio.h> to use the function in your program.
112     // But before submission, you must remove the freopen function or rewrite comment symbols(//).
113 
114     freopen("input.txt", "r", stdin);
115     cin >> T;
116     for (tc = 0; tc < T; tc++)
117     {
118         lowestPoint.x = INT_MAX;
119         lowestPoint.y = INT_MAX;
120         
121         cin >> pointNum;
122 
123         for (int i = 0; i < pointNum; i++)
124         {
125             cin >> points[i].x >> points[i].y;
126             //find the lowest point
127             if (lowestPoint.y > points[i].y || (lowestPoint.y == points[i].y && lowestPoint.x > points[i].x))
128             {
129                 lowestPoint.x = points[i].x;
130                 lowestPoint.y = points[i].y;
131                 lowestIndex = i;
132             }
133         }
134 
135         //swap lowestPoint to first place.
136         points[lowestIndex].x = points[0].x;
137         points[lowestIndex].y = points[0].y;
138         points[0].x = lowestPoint.x;
139         points[0].y = lowestPoint.y;
140 
141         sortPoints();
142 
143         graham();
144         cout << tc + 1 << endl;
145         cout << pointStack.size() << endl;
146         vector<Point> vec;
147         while (!pointStack.empty())
148         {
149             Point p = pointStack.top();
150             vec.push_back(p);
151             pointStack.pop();
152         }
153         for(vector<Point>::reverse_iterator iter=vec.rbegin(); iter!=vec.rend(); iter++)
154         {
155             cout << iter->x << " " << iter->y << endl;
156         }
157 
158     }
159 
160     return 0;//Your program should return 0 on normal termination.
161 }