luogu P1429 平面最近点对（加强版）

题目描述

给定平面上n个点，找出其中的一对点的距离，使得在这n个点的所有点对中，该距离为所有点对中最小的

输入输出格式

输入格式：

 

第一行：n；2≤n≤200000

接下来n行：每行两个实数：x y，表示一个点的行坐标和列坐标，中间用一个空格隔开。

 

输出格式：

 

仅一行，一个实数，表示最短距离，精确到小数点后面4位。

 

输入输出样例

输入样例#1： 复制

3
1 1
1 2
2 2

输出样例#1： 复制

1.0000

说明

0<=x,y<=10^9

题目链接:https://www.luogu.org/problem/show?pid=1429

解题报告:

分治经典题，复杂度O(nlogn).

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
#define db double
#define BIG 400011
#define ll long long
class point{
	public:
	db x=0,y=0;
	inline bool operator<(point A)const{
		return x<A.x||(x==A.x)&&(y<A.y);
	}
	inline db operator-(point A)const{
		return (db)(sqrt((db)(x-A.x)*(x-A.x)+(db)(y-A.y)*(y-A.y)));
	}
	private:
}p[BIG],b[BIG];
inline db Qmin(db a,db b){
	return a<b?a:b;
}
db ans=1000000000.00;
inline void merge(int l,int r){
	if(l==r)return;
	int mid=l+r>>1,t=0,pos=1;
	merge(l,mid);merge(mid+1,r);
	db line=p[mid].x;
	FOR(i,l,mid)if(line-p[i].x<ans)b[++t]=p[i];
	FOR(i,mid+1,r){
		if(p[i].x-line>=ans)continue;
		while(p[i].x-b[pos].x>=ans&&pos<=t)++pos;
		for(register int j=pos;j<=t&&p[i].x-b[j].x<ans;++j)ans=Qmin(p[i]-b[j],ans);
	}
}
int n;
int main(){
	scanf("%d",&n);
	FOR(i,1,n)
        scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+n+1);
	merge(1,n);
	printf("%.4lf\n",ans);
	return 0;
}