POJ 3741 Raid （平面最近点对）

$ POJRaid $ （平面最近点对）

---

---

$ solution: $

有两种点，现在求最近的平面点对。这是一道分治板子，但是当时还是想了很久，明明知道有最近平面点对，但还是觉得有点不对劲。基本算法专题出最近平面点对？怎么感觉我 $ Noip $ 凉了？ 这题不会是个坑吧。。。。

嗯，不瞎扯了。来回顾一下分治求平面点对的过程，首先将点按横坐标排序，然后整个区间不断往下二分，回溯的时候归并排序（这其实我来再写一次题解的原因，以前写的都是快排，但必须承认归并的复杂度才是最稳最准的）。我们将两个区间合并时，从中间点想外扩 $ d $ 的距离，这个距离内的点才有可能更新答案，而且这个距离里的每个点都不会计算多次，这个是有证明的 。然后我们暴力计算即可。

---

---

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define rg register int

using namespace std;

int t,n;

struct su{

	db x,y;

	bool z;

	inline bool operator <(const su &yy){

		return x<yy.x;

	}

}a[200005],b[200005];

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar()))if(ch=='-')sign=1;

	while(isdigit(ch))res=res*10+(ch^48),ch=getchar();

	if(sign)return -res; else return res;

}

inline db dis(const su &x,const su &y){

	return pow((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y),0.5);

}

inline db ask(int sl,int sr){

	if(sl==sr)return 1e9;

	rg mid=(sl+sr)>>1;

	db d=min(ask(sl,mid),ask(mid+1,sr));

	rg l=sl,r=mid+1,tt=sl;

	while(l<=mid&&r<=sr)

		if(a[l].y<a[r].y)b[tt++]=a[l++];

		else b[tt++]=a[r++];

	while(l<=mid)b[tt++]=a[l++];

	while(r<=sr)b[tt++]=a[r++];

	for(rg i=r=sl;i<tt;++i){ a[i]=b[i];

		if(fabs(b[i].x-b[mid].x)>d)continue;

		while(r<=sr&&b[r].y-b[l].y<=d)++r;

		for(rg j=i+1;j<r;++j)

			if(b[j].z!=b[i].z&&fabs(b[j].x-b[mid].x)<=d)//这里不能少

				d=min(d,dis(b[i],b[j]));

	}return d;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	t=qr();

	while(t--){

		n=qr();

		for(rg i=1;i<=n;++i)

			a[i].x=qr(),a[i].y=qr(),a[i].z=1;

		for(rg i=n+1;i<=n<<1;++i)

			a[i].x=qr(),a[i].y=qr();

		sort(a+1,a+2*n+1);

		printf("%.3lf\n",ask(1,2*n));

	}

	return 0;

}