【HDOJ】P1007 Quoit Design （最近点对）

题目意思很简单，意思就是求一个图上最近点对。

具体思想就是二分法，这里就不做介绍，相信大家都会明白的，在这里我说明一下如何进行拼合。

具体证明一下为什么只需要检查6个点

首先，假设当前左侧和右侧的最小值为d，那么对于一个点，如果有个最小值小于d，那么一定存在于上d下d左d右d的一块区域内，又因为是从左到右，从上到下，所以左侧的那部分匹配的区域会重叠，也就是对于左侧的区域，完全没有必要去进行匹配。所以只需要对右侧d，上下d的区域进行匹配，而假设这个区域内的所以点的距离为d那么最多为6个，那么如果长度小于d那么根据抽屉原理可以知道最多为6个。

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cmath>

#define MaxN 100001

using namespace std;

int N,t[MaxN],k;

struct Posi{

	double x,y;

}point[MaxN];

bool compoint(Posi a,Posi b){

	return a.x!=b.x?a.x<b.x:a.y<b.y;

}

bool comp(int a,int b){

	return point[a].y<point[b].y;

}

inline double dist(int a,int b){

	return sqrt((point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));

}

double solve(int l,int r){

	if (l==r) return 1e30;

	if (l+1==r) return dist(l,r);

	int mid=(l+r)>>1;

	double ld=solve(l,mid);

	double rd=solve(mid+1,r);

	double d=min(ld,rd);

	k=0;

	for (int i=l;i<=r;i++)

		if (fabs(point[i].x-point[mid].x)<d) t[++k]=i;

	sort(t+1,t+k+1,comp);

	for (int i=1;i<k;i++)

		for (int j=i+1;j<=k && fabs(point[t[j]].y-point[t[i]].y)<d;j++){

			double newd=dist(t[i],t[j]);

			if (newd<d) d=newd;

		}

	return d;

}

int main(){

	while(cin>>N,N!=0){

		for (int i=1;i<=N;i++) scanf("%lf%lf",&point[i].x,&point[i].y);

		sort(point+1,point+N+1,compoint);

		printf("%.2lf\n",solve(1,N)/2);

	}

	return 0;

}