问题介绍
给定平面上一些点的集合，找到一些点，使得这些点形成一个凸的包围，围住所有的点，如图
思路
采用分治法，将点集合一分为二，整体的凸包问题可以分为【求上半部分的凸包】+【求下半部分的凸包】
分策略
将集合一分为二的策略是：将点按照x升序排序，x相同则按y升序，然后选取0和最后一个下标，以这两点做一条直线，这两点一定是最左边和最右边的，我们用 pa 和 pb 表示这两点
为子问题求解划分范围
已经将集合一分为二了，那么子问题的求解区间该怎么划定呢？
遍历所有的点
- 找到在【直线pa pb】上方，距离【直线pa pb】最远的点 pmax
- 找到在【直线pa pb】下方，距离【直线pa pb】最远的点 pmin
最远距离表示
这个距离我们可以用他们三点组成的三角形的面积来表示，这个行列式可以求解，值得注意的是，p1一定是在p2左边，p1，p2组成直线，p3是我们要判断的那个点
- 最后得出的值大于0，说明 p3 在【直线 p1 p2】上方
- 最后得出的值小于0，说明 p3 在【直线 p1 p2】下方
- 最后得出的值等于0，说明 p3 在【直线 p1 p2】上
我们找到在【直线pa pb】上方，距离【直线pa pb】最远的点 pmax，找到在【直线pa pb】下方，距离【直线pa pb】最远的点 pmin，将 pa， pb， pmax， pmin 连起来，得到如下的图
把 【直线 pa pmax 】上方的点作为下一次查找的集合 s1
把 【直线 pmax pb 】上方的点作为下一次查找的集合 s2
把 【直线 pa pmin 】下方的点作为下一次查找的集合 s3
把 【直线 pmin pb 】下方的点作为下一次查找的集合 s4
分别递归四个区域点的集合，值得注意的是
使用points数组存储点
使用vis数组，表示下标为 i 的点是不是凸包上的点，vis[i] = 1则是
- 递归的边界情况，点集合的数目小于3，说明所有点都在凸包上，vis 置 1
- 在直线上的点，也要加入下一次的点的集合
- 如果递归的是上半部分的集合，那么之后的所有递归都只用针对上半部分，递归 s1 s2
- 如果递归的是下半部分的集合，那么之后所有的递归都只用针对下半部分，递归 s3 s4
- 如果递归的是全体集合（只有第一次递归会发送这个情况），需要同时递归上下部分，即同时递归 s1 s2 s3 s4
代码
输入：
12
1 1
1 2
2 0
2 1
2 3
3 1
3 3
4 0
4 2
5 1
5 4
6 2
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
输出
(1, 1)
(1, 2)
(2, 0)
(2, 3)
(4, 0)
(5, 1)
(5, 4)
(6, 2)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
#include <bits/stdc++.h>
using namespace std;
// 结构定义
typedef struct p
{
int x, y;
}p;
bool cmp(const p& p1, const p& p2)
{
if(p1.x==p2.x) return p1.y<p2.y;
return p1.x<p2.x;
}
// 存放点
p points[100];
int vis[100];
// 计算p1,p2,pi三个点组成的三角形面积
int peak(p p1, p p2, p pi)
{
return p1.x*p2.y + pi.x*p1.y + p2.x*pi.y - pi.x*p2.y - p2.x*p1.y - p1.x*pi.y;
}
// 递归求凸包
// ps 是当前要求解的点的集合，ps保存这些点在points数组中的下标
// mode 表示递归s1 s2，还是递归s3，s4，还是同时递归 s1，s2，s3，s4
// mode = 3 递归 s1，s2，s3，s4，只有第一次调用会出现该情况
// mode = 2 递归s3，s4
// mode = 1 递归s1 s2
void hull(vector<int> &ps, int mode)
{
// 边界处理：少于两个点的集合一定是凸包上的点
if(ps.size()<=2)
{
for(int i=0; i<ps.size(); i++) vis[ps[i]]=1;
return;
}
// 最左右一定是凸包上的点， pa最左点，pb最右点
vis[ps.front()]=1, vis[ps.back()]=1;
p pa=points[ps.front()], pb=points[ps.back()];
// 找距离 pa，pb组成的直线最远的点，imax是上方最远，imin是下方最远
int maxs=INT_MIN, mins=INT_MAX, imax=-1, imin=-1;
for(int i=1; i<ps.size()-1; i++)
{
int s = peak(pa, pb, points[ps[i]]);
if(s>maxs && s>=0) maxs=s, imax=ps[i];
if(s<mins && s<=0) mins=s, imin=ps[i];
}
// pa,pb与imax，imin的连线，分割出下一趟递归的点集合 s1 s2 s3 s4
vector<int> s1, s2, s3, s4;
for(int i=0; i<ps.size()-1; i++)
{
if(peak(pa, points[imax], points[ps[i]])>=0) s1.push_back(ps[i]);
if(peak(pa, points[imin], points[ps[i]])<=0) s3.push_back(ps[i]);
}
for(int i=1; i<ps.size(); i++)
{
if(peak(points[imax], pb, points[ps[i]])>=0) s2.push_back(ps[i]);
if(peak(points[imin], pb, points[ps[i]])<=0) s4.push_back(ps[i]);
}
if(mode==3)
hull(s1, 1), hull(s2, 1), hull(s3, 2), hull(s4, 2);
else if(mode==1) hull(s1, 1), hull(s2, 1);
else if(mode==2) hull(s3, 2), hull(s4, 2);
}
int main()
{
int n, x, y;
cin>>n;
vector<int> ps(n);
for(int i=0; i<n; i++)
cin>>points[i].x>>points[i].y, ps[i]=i;
sort(points, points+n, cmp);
hull(ps, 3);
for(int i=0; i<n; i++)
if(vis[i]==1) cout<<"("<<points[i].x<<", "<<points[i].y<<")"<<endl;
return 0;
}
/*
12
1 1
1 2
2 0
2 1
2 3
3 1
3 3
4 0
4 2
5 1
5 4
6 2
*/
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106