欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Raid POJ - 3714(平面最近点对+分治+归并)

程序员文章站 2022-03-30 08:40:59
...

题意:传送门
题解:首先得了解平面最近点对的求法,采用分治求法,按照x轴排序后,分为左右两部分,最近点对要么在左边,要么在右边,要么就是中间合并起来,中间这块可以按照yy坐标轴排序,通过卡死纵轴大小的矩形那种达到O(n)O(n)合并,如果按照yy坐标轴排序的话,最后每次维护排序加维护O(nlogn)O(nlogn),一共要分治lognlogn次,总复杂度O(nlog2n)O(nlog^2n),但是每次合并时可以用归并排序的思想,使之每次达到O(n)O(n),最终复杂度为O(nlogn)O(nlogn),这个题可以求距离时看下是相同类型的点,返回infinf,如果不同的点,再返回distdist,但是这种做法出题人可能依旧会卡人,比如左边都放一种点,右边都放一种点,可能达到O(n2)O(n^2),所以可以提前将所有点旋转一个角度,公式参考这个传送门
codecode:

#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;
}