凸包问题的分治法
一,思想挺简单的,这里我觉得这篇博客还不错https://blog.csdn.net/zbspy_ZJF/article/details/78814800
看了很多的博客,总觉得代码有点乱(可能是个人水平有限吧),于是吧自己就写了一篇:
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100*1000+10
struct point { int x, y; };
int N,vis[MAXN];
vector<point>p,v;
bool cmp(point a, point b) { return a.x < b.x; }
int get_area(point p1,point p2,point p3) {
return p1.x*p2.y + p3.x*p1.y + p2.x*p3.y - p3.x*p2.y - p2.x*p1.y - p1.x*p3.y;
}
void deal(point p1,point p2,vector<point> p) {
if (p.size() == 0) {
v.push_back(p1);
return;
}
int area = 0,index;
vector<point>L, R;
for (int i = 0; i < p.size(); i++) {
int are = get_area(p1,p2,p[i]);
if (are > area) {
area = are;
index = i;
}
}
for (int i = 0; i < p.size(); i++) {
if (get_area(p1, p[index], p[i]) > 0)L.push_back(p[i]);
else if (get_area(p[index], p2, p[i]) > 0)R.push_back(p[i]);
}
deal(p1,p[index],L);
deal(p[index],p2,R);
}
void solve() {
sort(p.begin(), p.end(), cmp);
point p1 = *p.begin(), p2 = *(p.end()-1);
vector<point>L, R;
for (int i = 0; i <p.size(); i++) {
int area = get_area(p1, p2, p[i]);
if (area > 0)L.push_back(p[i]);
else if (area < 0)R.push_back(p[i]);
}
deal(p1,p2,L);
deal(p2,p1,R);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << "\t\t请输入点的个数:";
cin >> N;
point po;
for (int i = 1; i <= N; i++) {
cout << "\t\t请输入第" << i << "个点的坐标";
cin >> po.x >> po.y;
p.push_back(po);
}
solve();
cout << "\t\t凸包上的点为:" << endl;
for (int i = 0; i < v.size(); i++)cout << v[i].x << ' ' << v[i].y << endl;
return 0;
}