平面最近点对

模板题

P1429 平面最近点对（加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P7883 平面最近点对（加强加强版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解

#include<bits/stdc++.h>
using namespace std;
const int MAX = 400010;

struct point{
	double x,y;
}p[MAX];

int n;
double ans;

bool equal(double a, double b){
	return fabs(a - b) <= 1e-6;
}

bool cmpx(point &a, point &b){ //按x排序
	if(!equal(a.x, b.x)) return a.x < b.x;
	else return a.y < b.y;
}

bool cmpy(point &a, point &b){ //按y排序
	return a.y < b.y;	
}

double dist(point &a, point &b){ 
	return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

double solve(int l, int r){
	double res = 1e300;
	if(l==r){
		return res;
	}else{
		int mid = (l+r)/2;
		double midx = p[mid].x;
		res = min(res, solve(l, mid)); //左侧最小距离
		res = min(res, solve(mid+1, r)); //右侧最小距离
        //两点分别位于左右两侧的最小距离
		vector<point> v;
		for(int i = l ; i <= r ; i ++){
			if(fabs(p[i].x - midx) <= res){
				v.push_back(p[i]);
			}
		}
		sort(v.begin(),v.end(),cmpy);
		for(int i = 0 ; i < v.size() ; i ++){
			for(int j = i+1 ; j < v.size() && v[j].y - v[i].y < res; j ++){
				res = min(dist(v[i], v[j]), res);
			}
		}
	}
	return res;
}

int main(void){
	scanf("%d", &n);
	for(int i = 0 ; i < n ; i ++){
		scanf("%lf %lf", &p[i].x , &p[i].y);
	}
	sort(p,p+n, cmpx);
	ans = solve(0, n-1);
	printf("%.lf", ans*ans);
	return 0;
}