最近点对问题（分治法以及蛮力法的运用）

1.问题
数学语言：设p1=(x1,y1),p2=(x2,y2)…pn=(xn,yn)是平面n上n个点构成的集合S，找出集合S中距离最近的点对就是集合里的最小点对，两者的距离就是最小对距离。
2.解析
（1）将集合S分成两个子集S1和S2，每个子集中大约有n/2个点，设集合S的最近点对是pi和pj(1<=i,j<=n）则有以下三种情况
1.pi∈S1,pj∈S1
2.pi∈S1,pj∈S2
3.pi∈S2, pj∈S2
（2）通过直线x=mid（（L+R）/2）,将空间划为两部分,x<mid和x>mid分别求出左右最近点对距离，d1,d2,另d=min(d1,d2) 则，只需考虑3,即x-d和x+d的区域之间的最近点对，按照Y坐标对区域内点进行排序，如果一个点对的距离小于d,他们一定在d*(2*d)的区域内。
3.设计

1.如果输入的点数n<=3，直接使用暴力法解决问题。
2.当n>3时，使用分治策略解决问题。
int mid = (R + L) / 2, l = L, r = R;//取中位数，进行分治
	点与点之间没有其他点时
		返回两点之间距离；
	if 点与点之间还有一个点 
		返回其中距离最小的两点之间的距离；
	double d1 = getmin2(p, L, mid), d2 = getmin2(p, mid + 1, R);//继续对区间进行划分
	double d = min(d1, d2);
	while (p[l].x < p[mid].x - d && l <= R);
		l++;
	while (p[r].x > p[mid].x + d && r >= L)
		r++;
	对区间内的点根据y的大小进行排序；
	for (int i = l; i <= r; i++) {
//依次计算S[l...r]的最近点对(考察y-p[mid].y<d的点)
for (int j = i + 1; j <= r; j++) {
			if (p[j].y - p[i].y >= d) {
				break;
			}
			else {
				t = dis(p[i], p[j]);
				if (t < d)
					d = t;
			}
		}
	}
返回值为t；

4.分析
T(n)=1 n<=3
T(n)=2T(n/2)+O(n)​ n>3​
5.源码

#include<map>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
#define ll long long
int i, j, k;
int n, m;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
struct point {
	double x, y;
}p[maxn];
double dis(point p1, point p2) {
	return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
bool cmp1(point p1, point p2) {
	return p1.x < p2.x;
}
bool cmp2(point p1, point p2) {
	return p1.y < p2.y;
}
//蛮力法
double getmin(int n) {
	double minn = sqrt((p[0].x - p[1].x)*(p[0].x - p[1].x) + (p[0].y - p[1].y)*(p[0].y - p[1].y));
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			double t = sqrt((p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y));
			if (minn > t)
				minn = t;
		}
	}
	return minn;
}
//分治法
double getmin2(point p[], int L, int R) {
	int mid = (R + L) / 2, l = L, r = R;
	if (R - L == 1) {
		return dis(p[R], p[L]);
	}
	if (R - L == 2) {
		double d1 = dis(p[R], p[L]), d2 = dis(p[R], p[R + 1]), d3 = dis(p[R + 1], p[L]);
		return min(min(d1, d2), d3);
	}
	double d1 = getmin2(p, L, mid), d2 = getmin2(p, mid + 1, R);
	double d = min(d1, d2);
	while (p[l].x < p[mid].x - d && l <= R);
		l++;
	while (p[r].x > p[mid].x + d && r >= L)
		r++;
	sort(p + 1, p + r + 1, cmp2);
	double t;
	for (int i = l; i <= r; i++) {
		for (int j = i + 1; j <= r; j++) {
			if (p[j].y - p[i].y >= d) {
				break;
			}
			else {
				t = dis(p[i], p[j]);
				if (t < d)
					d = t;
			}
		}
	}
	return d;
}
int main() {
	cin >> n;
	for (i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	sort(p + 1, p + n + 1, cmp1);
	for (i = 1; i <= n; i++) {
		cout << p[i].x << " " << p[i].y << endl;
	}
	if(n<=3)
		cout << getmin(n) << endl;
	else
		cout << getmin2(p, 1, n) << endl;
	return 0;
}

源代码已在git维护：https://github.com/myycjw/minpoint