钱柜娱乐 > 其他 > 详细

R的农场(平面最近点对)

时间:2019-02-11 18:18:56      阅读:61      评论:0      收藏:0      [点我收藏+]

标签:现在   struct   cmp   有一个   我只   推荐   n)   ref   归并排序   

本题实质上要求平面最近点对,推荐一篇博客

有一片农场,R购买了N个守卫,分别让他们站在一定的位置上(守卫不可移动,同一位置上至多有一个守卫).但是守卫们彼此十分厌恶.经研究,当某两个守卫距离≤K,他们就会发生争吵;而想要守卫们和解也不难,只需要R给出的平均工资能使两人满意,他们就会同意和解并成为朋友;当然,如果两个守卫有共同的朋友,他们也会和解成为朋友.R非常不想守卫们争吵,因此他想找出,在能使所有守卫闭嘴的前提下,平均工资的最小值是多少?

题意:平面上有N个点,某些点之间有无向边相连.求出最小的w,使得选择了所有权值≤w的边之后,D=min{dis(u, v)?|?u,v不连通}≥K.

分析:首先,钱柜娱乐官网可以将m对有厌恶关系的守卫,看作它们之间有一条权值为w的边,用并查集维护点与点之间的连通性.不难发现,答案具有可二分性,因为D(w)一定会是一个关于平均工资w的单增函数,于是钱柜娱乐官网可以对每条边按照w从小到大排序,然后二分w,再\(n^2\)暴力地求最近点对,判断合法性.

现在钱柜娱乐官网要考虑如何高效地求平面内最近点对,文顶已经推荐了一篇博客,我只简述方法了.

运用分治法,设work(V)为点集V中的最近点对的距离.那么,要求点集V的最近点对,钱柜娱乐官网先对其按x坐标从小到大排序,然后考虑选择一条垂直分割线,把V划分为点数尽可能相等的两部分V1和V2(说直白了就是选择点集V最中间两个点的中线).则work(V)=min{work(V1),solve(V2), dis(u,v)?|?u∈V1,v∈V2}

如何理解这个式子?关于点集V中的最近点对,无非只有三种情况,两个点都在V1中,两个点都在V2中,或者一个点在V1中,另一个点在V2中.前两种情况就是分治的子问题,那么第三种情况如何高效求解呢?

令d=min{work(V1),work(V2)},那么钱柜娱乐官网可以只需要考虑已经选择好的垂直分割线往两端各延伸d的这一个区域,因为只有这个区域内的点对才可能有比d更小的距离(这里不懂的话,画个图就明白了)


work(V){
    选择一条垂直分割线,它将V分割为V1,V2;
    d=min(work(V1),work(V2));
    取出垂直分割线往两端延伸d的区域内的所有点;
    求出区域内最近距离d’;
    return min(d,d’);
}

到了这里,问题只剩最后一步,如何求出区域内最近距离d’,上面那一段文字只是优化了时间复杂度,仍未提到具体地如何做?对于区域内的点,钱柜娱乐官网对其按y坐标排序;对于每个点,找到y坐标与它相差不超过d的点,比较最近距离d’.

#include<bits/stdc++.h>
using namespace std;
int n,m,fa[100005];
double k;
struct point{//记录每个守卫信息的结构体
    double x,y;int id;
}a[100005],b[100005];
struct edge{//记录每一对有关系守卫信息的结构体
    int x,y;double w;
}e[200005];
bool cmp1(edge x,edge y){return x.w<y.w;}
bool cmp2(point x,point y){return x.x<y.x;}
bool cmp3(point x,point y){return x.y<y.y;}
int find(int x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}//并查集的路径压缩找爸爸操作,没的说
double dis(point x,point y){
    return max(fabs(x.x-y.x),fabs(x.y-y.y));
}//求两个点之间的(切比雪夫)距离的函数
double work(int l,int r){
    if(l==r)return 1e18;
//分治边界:该区间左右边界重合,最近点对距离视为无穷大
    int mid=(l+r)>>1,i=l,j=mid+1,k=i;
    double midline=(a[mid].x+a[mid+1].x)/2;
//midline垂直分割线
    double now=min(work(l,mid),work(mid+1,r));
    double d=now;
//归并排序:按照y坐标排序
    while(i<=mid&&j<=r){
        if(cmp3(a[i],a[j]))b[k]=a[i],i++,k++;
        else b[k]=a[j],j++,k++;
    }
    if(i<=mid)while(i<=mid)b[k]=a[i],i++,k++;
    else while(j<=r)b[k]=a[j],j++,k++;
    for(int i=l;i<=r;i++)a[i]=b[i];
    int L=1,R=0;
    for(int i=l;i<=r;i++)
        if(fabs(a[i].x-midline)<=d){
            while(L<=R&&(a[i].y-b[L].y)>=d)
                L++;
            for(int j=L;j<=R;j++){
                int x=find(a[i].id);
                int y=find(b[j].id);
                if(x!=y)
                    now=min(now,dis(a[i],b[j]));
            }
            b[++R]=a[i];
        }
    return now;
}
bool check(int mid){
    for(int i=1;i<=n;i++)fa[i]=i;//并查集
//因为钱柜娱乐官网的w二分到了第mid对点所要求的,
//所以第1-mid对点都能被满足要求,和解成为朋友
    for(int i=1;i<=mid;i++){
        int x=find(e[i].x),y=find(e[i].y);
        if(x!=y)fa[y]=x;
    }
    sort(a+1,a+n+1,cmp2);
//按照点的横坐标位置从小到大排序
    return work(1,n)>k;
//函数work返回的是当前w下,最近的两个点间距
}
int main(){
    scanf("%d%d%lf",&n,&m,&k);
//n个点,m对点之间有无向边相连,点之间最小距离要求是k
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&a[i].x,&a[i].y);
        a[i].id=i;
    }//读入每个点的横纵坐标
    for(int i=1;i<=m;i++)
        scanf("%d%d%lf",&e[i].x,&e[i].y,&e[i].w);
//读入有边相连的一对点:编号x,y及边权w
    sort(e+1,e+m+1,cmp1);
//按照边权从小到大排序,方便二分
    int l=0,r=m,mid,ans;//注意l的初始值
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%.3lf\n",e[ans].w);
    return 0;
}

R的农场(平面最近点对)

标签:现在   struct   cmp   有一个   我只   推荐   n)   ref   归并排序   

原文:https://www.cnblogs.com/PPXppx/p/10362626.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 ♞钱柜娱乐_钱柜娱乐777_钱柜娱乐唯一授权官网-欢迎您
打开钱柜娱乐技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号