平面最近点对(加强版)

传送门

ovo原来简单版的非常的好做,只要肆意暴力枚举即可。

不过这道题的数据范围变成了200000,即使是洛谷神机也跑不过去的。

于是乎我们考虑分治法。

对于一个平面上的所有点,我们设其属于一个点集S。我们想要把点集S尽可能平均的分成两个点集,那么我们只要每次取当前点集中所有点的中位数进行分割即可。

记录dis表示一个点集之内两点的最短距离。对于一个点集S,将其分解为两个点集S1,S2之后,我们假设现在已经求出来S1的dis1,S2的dis2.那么当前的答案d=min(dis1,dis2),之后如果在S1,S2中还有点对的距离<d,那么一定分属于两个点集。

这个时候可以从中间的分割线分别向两边引出一条长度为d的矩形(记为C1,C2),能更新最近距离的点对一定分属于这两个矩形。然而单单这么分析的话最坏的复杂度仍然可能非常大。那我们用dis的性质来考虑一下,对于C1中的每一个点k,能与之配对更新最短距离的,一定是C2中一个长为dis,高为2*dis的一个矩形之内的点。再者,因为S2中每两个点的距离必须>=dis,所以这个矩形之内最多只可能有6个点。

也就是说对于C1中的每一个点k,最多只有6个点可以与之更新最短距离。那我们直接枚举这六个点并且更新就可以了。

所以我们一开始先把所有的点按照横坐标排序,先进行分割,之后分割到边界之后进行回溯合并,合并的时候我们枚举所以离中线的距离<=dis的点计入C1,C2,之后把这些点按照y值排序,之后进行配对更新即可,遇到不符合的情况要直接跳出,否则会T。(我就纳闷为什么照着人家写能慢了一倍)

看一下跑的贼慢的代码。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
using namespace std;
typedef long long ll;
const int M = 200005;
const double INF = 9999999999;
int n,L,f[M],dp[M]; 
int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >='0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct node
{
    double x,y;
    bool operator < (const node &g) const
    {
        if(x == g.x) return y < g.y;
        return x <  g.x;
    }
}s[M];

bool cmp(int a,int b)
{
    return s[a].y < s[b].y;
}

double dist(int p,int q)
{
    return sqrt((s[p].x - s[q].x)*(s[p].x - s[q].x) + (s[p].y - s[q].y) * (s[p].y - s[q].y));
}

double merge(int l,int r)
{
    double d = INF;
    if(l == r) return d;
    if(l+1 == r) return dist(l,r);//如果只有两个点就返回其间的距离
    int mid = (l+r) >> 1;
    double d1 = merge(l,mid);
    double d2 = merge(mid+1,r);
    d = min(d1,d2);
    int k = 0;
    rep(i,l,r) if(fabs(s[mid].x - s[i].x <= d)) f[++k] = i;//记录所有离中线不超过dis的点
    sort(f+1,f+1+k,cmp);
    rep(i,1,k)
    rep(j,i+1,k)
    {
    if(s[f[j]].y - s[f[i]].y >= d) break;
    double d3 = dist(f[i],f[j]);
    d = min(d,d3);//进行答案更新
    }
    return d;
}

int main()
{
    n = read();
    rep(i,1,n) scanf("%lf %lf",&s[i].x,&s[i].y);
    sort(s+1,s+1+n);
    printf("%.4lf
",merge(1,n));
    return 0;
}

还有dalao跑的快一倍的代码。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000001 ;
const int INF=2<<20;
int n,temp[maxn];
struct Point
{
    double x,y;
}S[maxn];

bool cmp(const Point &a,const Point&b)
{
    if(a.x==b.x)
        return a.y<b.y;
    else
        return a.x<b.x;
}

bool cmps(const int &a,const int &b)
{
    return S[a].y<S[b].y ;
}

double min(double a,double b)
{
  return a<b?a:b;
}

double dist(int i,int j)
{
    double x=(S[i].x-S[j].x)*(S[i].x-S[j].x);
    double y=(S[i].y-S[j].y)*(S[i].y-S[j].y);     
    return sqrt(x+y);
}

double merge(int left,int right)
{
    double d=INF;
    if(left==right)
        return d ;
    if(left+1==right) 
        return dist(left,right);
    int mid=left+right>>1;
    double d1=merge(left,mid) ;
    double d2=merge(mid+1,right) ;
    d=min(d1,d2);
    int i,j,k=0;
    for(i=left;i<=right;i++)
        if(fabs(S[mid].x-S[i].x)<=d)
            temp[k++]=i;
    sort(temp,temp+k,cmps);
    for(i=0;i<k;i++)
        for(j=i+1;j<k&&S[temp[j]].y-S[temp[i]].y<d;j++)
        {
            double d3=dist(temp[i],temp[j]); 
            if(d>d3)
                d=d3;
        }
    return d;
}

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%lf%lf",&S[i].x,&S[i].y);
    sort(S,S+n,cmp);
    return !printf("%.4lf
",merge(0,n-1));
}

Published by

风君子

独自遨游何稽首 揭天掀地慰生平

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注