【poj3714】 Raid

时间：2024-11-29 10:37:55

http://poj.org/problem?id=3714 (题目链接)

现在才搞平面最近点对。。感觉有点尴尬

题意

　　给出平面上两组点，每组n个，求两组点之间最短距离

Solution1

　　平面最近点对，分治即可。

　　将点按横坐标排序，然后每次二分成左边和右边分别计算最小距离，再计算中间的最小距离，这里需要把中间符合条件的点按照纵坐标排序，然后当当前枚举的两点的纵坐标之差大于答案时break，否则会TLE。

代码1

// poj3714

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=1000010;

struct point {double x,y;int flag;}p[maxn];

int n,tmp[maxn];

bool cmpx(point a,point b) {

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

}

bool cmpy(int a,int b) {

    return p[a].y==p[b].y ? p[a].x<p[b].x : p[a].y<p[b].y;

}

double dis(point a,point b) {

    return sqrt((double)(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double solve(int l,int r) {

    double res=1e60;

    if (l==r) return res;

    if (l+1==r) {

        if (p[l].flag==p[r].flag) return res;

        return dis(p[l],p[r]);

    }

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

    res=solve(l,mid);

    res=min(res,solve(mid+1,r));

    int num=0;

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

        if (fabs(p[i].x-p[mid].x)<=res) tmp[++num]=i;

    sort(tmp+1,tmp+num+1,cmpy);

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

        for (int j=i+1;j<=num;j++) {

            if (fabs(p[tmp[i]].y-p[tmp[j]].y)>=res) break; //剪枝

            if (p[tmp[i]].flag!=p[tmp[j]].flag) res=min(res,dis(p[tmp[i]],p[tmp[j]]));

        }

    return res;

}

int main() {

    int T;

    scanf("%d",&T);

    while (T--) {

        scanf("%d",&n);

        for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y),p[i].flag=0;

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

        n<<=1;

        sort(p+1,p+1+n,cmpx);

        printf("%.3f\n",solve(1,n));

    }

    return 0;

}

Solution2

　　hzwer上惊现平面最近点对的随机化算法（貌似是随机分块），于是我就蒯了过来，虽然并不知道为什么可以这样写，但是好像很厉害的样子。

　　上网搜了下，发现期望复杂度是O（n）的。度娘链接

　　然而= =：

　　　　【poj3714】 Raid

　　比分治还跑的慢，坑比东西。

代码2

// poj3714

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    int f,x=0;char ch=getchar();

    while (ch<='0' || ch>'9') {if (ch=='-') f=-1;else f=1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=1000010;

struct point {double x,y;int flag;}p[maxn];

int n,block,m;

bool cmp(point a,point b) {

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

}

point rotate(point a,double x) {

    return (point){(double)a.x*cos(x)-(double)a.y*sin(x),(double)a.y*cos(x)+(double)a.x*sin(x),a.flag};

}

double dis(point a,point b) {

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

}

int main() {

    int T;scanf("%d",&T);

    while (T--) {

        scanf("%d",&n);

        for (int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y),p[i].flag=0;

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

        n<<=1;

        block=(int)sqrt(n);

        m=n/block+(n%block!=0);

        double t=rand()/10000;

        for (int i=1;i<=n;i++) p[i]=rotate(p[i],t);

        sort(p+1,p+1+n,cmp);

        double ans=1e60;

        for (int i=1;i<=m;i++) {

            int t1=block*(i-1),t2=min(block*i,n);

            for (int j=t1;j<=t2;j++)

                for (int k=t1+1;k<=t2;k++) if (p[j].flag!=p[k].flag) ans=min(ans,dis(p[j],p[k]));

        }

        printf("%.3f\n",ans);

    }

    return 0;

}

　　

相关文章