Raid POJ - 3714(平面最近点对+分治+归并)
程序员文章站
2022-03-30 08:40:59
...
题意:传送门
题解:首先得了解平面最近点对的求法,采用分治求法,按照x轴排序后,分为左右两部分,最近点对要么在左边,要么在右边,要么就是中间合并起来,中间这块可以按照坐标轴排序,通过卡死纵轴大小的矩形那种达到合并,如果按照坐标轴排序的话,最后每次维护排序加维护,一共要分治次,总复杂度,但是每次合并时可以用归并排序的思想,使之每次达到,最终复杂度为,这个题可以求距离时看下是相同类型的点,返回,如果不同的点,再返回,但是这种做法出题人可能依旧会卡人,比如左边都放一种点,右边都放一种点,可能达到,所以可以提前将所有点旋转一个角度,公式参考这个传送门
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int N=2e5+5;
const double inf=1e9;
int T,n;
struct point{
int x,y,type;
bool operator < (const point &a)const{
return x<a.x;
}
}points[N],temp[N];
double dist(point a,point b)
{
if(a.type==b.type)return inf;
double dx=a.x-b.x,dy=a.y-b.y;
return sqrt(dx*dx+dy*dy);
}
double dfs(int l,int r)
{
if(l>=r)return inf;
int mid=(l+r)>>1;
double mid_x=points[mid].x;
double res=min(dfs(l,mid),dfs(mid+1,r));
{
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r){
if(points[i].y<=points[i].y)temp[k++]=points[i++];
else temp[k++]=points[j++];
}
while(i<=mid)temp[k++]=points[i++];
while(j<=r)temp[k++]=points[j++];
for(int i=0,j=l;i<k;i++,j++)points[j]=temp[i];
}
int k=0;
for(int i=l;i<=r;i++){
if(points[i].x>=mid_x-res&&points[i].x<=mid_x+res)temp[k++]=points[i];
}
for (int i = 0; i < k; i ++ )
for (int j = i - 1; j >= 0 && temp[i].y - temp[j].y < res; j -- )
res = min(res, dist(temp[i], temp[j]));
return res;
}
int main()
{
T=read();
while(T--){
n=read();
for(int i=0;i<n;i++){
points[i].x=read();points[i].y=read();
points[i].type=0;
}
for(int i=n;i<n*2;i++){
points[i].x=read();points[i].y=read();
points[i].type=1;
}
sort(points,points+2*n);
printf("%.3f\n",dfs(0,2*n-1));
}
return 0;
}