凸包问题的分治法

一，思想挺简单的，这里我觉得这篇博客还不错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;
}