分治法的应用------凸包问题（easy-x图形化）

//分治法求凸包问题
#include<iostream>
#include<vector>
#include<algorithm>
#include<graphics.h>
#include<conio.h>
#include<map>
using namespace std;
const int maxn = 1e5 + 15;
const double eps = 1e-8;
int n = 0;
struct Point {
	double x, y;
}p[maxn], ans[maxn];
int visit[maxn], mark[maxn];
double Djudge(Point a1, Point a2, Point a3) {
	double calculate = a1.x * a2.y + a3.x * a1.y + a2.x * a3.y - a3.x * a2.y - a2.x * a1.y - a1.x * a3.y;
	return calculate;
}
bool cmpxy(const Point a, const Point b) {
	if (a.x != b.x)
		return a.x < b.x;
	else
		return a.y < b.y;
}
void DealLeft(int first, int last) {
	double max = 0;
	int index = -1;
	int i = first;
	if (first < last) {
		for (i = first + 1; i < last; i++){
			double calcu = Djudge(p[first], p[i], p[last]);
			if (calcu == 0) { visit[i] = 1; }
			if (calcu > max) {
				max = calcu;
				index = i;
			}

		}
	}
	else {
		for (i - 1; i > last; i--) {
			double calcu = Djudge(p[first], p[i], p[last]);
			if (calcu == 0) { visit[i] = 1; } //
			if (calcu > max) {
				max = calcu;
				index = i;
			}
		}
	}
	if (index != -1) {
		visit[index] = 1; 
		DealLeft(first, index);
		DealLeft(index, last);
	}
}
//点点，将所有点画在坐标轴上
void drow_graph(vector<pair<double, double> >& point, int n) {
	initgraph(800, 800);
	setbkcolor(WHITE);
	cleardevice();
	setlinecolor(BLUE);
	line(400, 0, 400, 800);
	line(0, 400, 800, 400);
	for (int i = 0; i < n; i++) {
		setfillcolor(RED);
		int x = point[i].first + 400;
		int y = 400 - point[i].second;
		fillcircle(x, y, 5);
	}
}

//连线，将所有点连起来
void connect_end(Point* point, int n) {
	setlinecolor(RED);
	setlinestyle(10);
	for (int i = 0; i < n - 1; i++) {
		int x1 = point[i].x + 400;
		int y1 = 400 - point[i].y;
		int x2 = point[i + 1].x + 400;
		int y2 = 400 - point[i + 1].y;
		line(x1, y1, x2, y2);
	}
	int x = point[0].x + 400;
	int y = 400 - point[0].y;
	int x1 = point[n - 1].x + 400;
	int y1 = 400 - point[n - 1].y;
	line(x, y, x1, y1);
	_getch();
	closegraph();
}
int dblcmp(double k) {
	if (fabs(k) < eps) return 0;
	return k > 0 ? 1 : -1;
}
double multi(Point p0, Point p1, Point p2) {
	return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
bool cmp(const Point& a, const Point& b) {
	return dblcmp(multi(ans[0], a, b)) > 0;
}
int main()
{
	vector<pair<double, double> > pointsArray(maxn);
	cout << "请输入点的个数：";
	cin >> n;
	cout << "请输入点的坐标：" << endl;
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y;
		visit[i] = 0;
		pointsArray[i] = make_pair(p[i].x, p[i].y);
	}
	drow_graph(pointsArray, n);
	visit[0] = 1;
	visit[n - 1] = 1;
	sort(p, p + n, cmpxy);
	DealLeft(0, n - 1); 
	DealLeft(n - 1, 0); 
	int t = 0;
	for (int i = 0; i < n; i++) {
		if (visit[i] == 1) {
			ans[t].x = p[i].x;
			ans[t].y = p[i].y;
			t++;
		}
	}
	sort(ans + 1, ans + t, cmp);
	connect_end(ans, t);
	return 0;
}