平面最近点对

灰太狼 2023-07-06 14:51 24阅读 0赞

一，平面最近点对

问题：在给n个平面上的点，让你找到最近的一对点。

暴力n\*n做法肯定超时。

我们考虑分治。

1-n这个区间，我们可以先找到A=（1-mid）和B=（mid+1,n）这个区间的最小点对。并一直递归下去。

现在主要的问题，在于如何对这两个区间进行合并操作。

因为，也许最近点对是A区间一个点B区间一个点。

我们可以继续考虑

合并这两个区间，我们有必要把这两个区间所有的点都拿来比较一下吗？

肯定是没有必要的。

假如当前所求的最小距离为minx，同时我们可以把a\[mid\]作为一个旗标。

A区间和B区间的点离旗标之间的距离如果大于minx。那我肯定就不用考虑了。

所以我们合并的时候要考虑的x范围是\[a\[mid\] - minx,a\[mid\] + minx\]。超过这个范围的x，距离一定会比minx大。

可是这样还不够，万一所考虑的区间很多点，那复杂度还是降不下来。

我们用考虑x的想法继续去考虑y。

对于一个点a的y来说，与点a的最近点b的y，一定不会离a的y差minx距离。

所以我们用这种方法可以把所考虑到的点降低到只有7个点。

为什么是7个点呢？

可看下面这篇证明：https://oi-wiki.org/geometry/nearest-points/

参考博客:https://www.cnblogs.com/kamimxr/p/11200473.html 大佬的图解很好懂了。

例题一：https://www.luogu.com.cn/problem/P1429

这题是裸题，可以做模板了。（逃，巨弱还是错了n次，痛

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    
    typedef struct Node{
        double x,y;
        int id;
    }Node;
    
    int n;
    Node node[200100];
    Node tran[200100];
    double minx = 1e20;
    
    bool same(double a, double b) { /// 1e-5精度意义下的浮点数相等
        if(fabs(a-b) <= 1e-5) return true; return false;
    }
    int cmpx(Node a,Node b){
          if(!same(a.x, b.x)) return a.x<b.x; return a.y<b.y;
    }
    int cmpy(Node a,Node b){
         if(!same(a.y, b.y)) return a.y<b.y; return a.x<b.x;
    }
    
    void dist_minx(Node a,Node b){
        double sum = sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
        minx = min(minx,sum);
    }
    
    void merge_node(int l,int mid,int r)
    {
        int t = 0;
        int i = l,j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(node[i].y < node[j].y)
            {
                tran[++ t] = node[i]; i ++; continue;
            } else {
                tran[++ t] = node[j]; j ++; continue;
            }
        }
        while(i <= mid) tran[++ t] = node[i ++];
        while(j <= r) tran[++ t] = node[j ++];
        for(int i = l; i <= r; i ++)
            node[i] = tran[i - l + 1];
    }
    
    void Blocking(int l,int r)
    {
        if(r - l <= 3)
        {
            for(int i = l; i < r; i ++)
            {
                for(int j = i + 1; j < r; j ++)
                {
                    dist_minx(node[i],node[j]);
                }
            }
            sort(node + l,node + r + 1,cmpy);
            return ;
        }
        int mid = (l + r) >> 1;
        double midx = node[mid].x;
        Blocking(l,mid); Blocking(mid + 1,r);
        merge_node(l,mid,r);
        vector<Node> Q;
        for(int i = l; i <= r; i ++)
        {
            if(fabs(node[i].x - midx) >= minx) continue;
            for(int j = Q.size() - 1; j >= 0; j --)
            {
                if(fabs(Q[j].y - node[i].y) >= minx) break;
                dist_minx(Q[j],node[i]);
            }
            Q.push_back(node[i]);
        }
        Q.clear();
        return ;
    }
    
    int main()
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++)
        {
            scanf("%lf%lf",&node[i].x,&node[i].y);
            node[i].id = i;
        }
        sort(node + 1,node + n + 1,cmpx);
        Blocking(1,n);
        printf("%0.4lf\n",minx);
    }

例题二：http://codeforces.com/problemset/problem/120/J

题意是要我们找到一对点：类似于最近点对的sqrt((xi+xj)^2 +(yi+yj)^2)使其值最小的点对。

观察可得，这个式子是不是跟两点间的距离就只差了一个符号。

那我们可以把式子转化为：sqrt((xi-(-xj))^2 +(yi-(-yj))^2)

在根据题意，一个点可以自由转化为带负数的形式。就可做了。

吐了，cmpx写错导致浪费了3个小时。

注意：你不能直接在求路径的时候加负数。这会导致你的y排序不满足的问题。

所以，我们应该在最后的时候在把k转换过来。

#include"stdio.h"
    #include"string.h"
    #include"vector"
    #include<bits/stdc++.h>
    #include"math.h"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
     
    typedef struct Node{
        ll x,y;
        int id,stae;
    }Node;
     
    int n;
    Node node[800100];
    Node tran[800100];
    ll minx = LONG_LONG_MAX;
    int v1,v2,s1,s2;
     
    int cmpx(Node a,Node b){
          if(a.x != b.x) return a.x<b.x; return a.y<b.y;
    }
    int cmpy(Node a,Node b){
        if(a.y == b.y) return a.x < b.x;
          return a.y<b.y;
    }
     
    void dist_minx(Node a,Node b){
        if(a.id == b.id) return ;
        ll sum = ((a.x - (b.x)) * (a.x - (b.x)) + (a.y - (b.y)) * (a.y - (b.y)));
        if(minx>sum)
        {
            minx = sum;
            v1 = a.id,v2 = b.id;
            s1 = a.stae;s2 = b.stae;
        } return ;
    }
     
    void merge_node(int l,int mid,int r)
    {
        int t = 0;
        int i = l,j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(node[i].y < node[j].y)
            {
                tran[++ t] = node[i]; i ++; continue;
            } else {
                tran[++ t] = node[j]; j ++; continue;
            }
        }
        while(i <= mid) tran[++ t] = node[i ++];
        while(j <= r) tran[++ t] = node[j ++];
        for(int i = l; i <= r; i ++)
            node[i] = tran[i - l + 1];
    }
     
    void Blocking(int l,int r)
    {
        if(r - l <= 5)
        {
            for(int i = l; i < r; i ++)
            {
                for(int j = i + 1; j <= r; j ++)
                {
                    dist_minx(node[i],node[j]);
                }
            }
            sort(node + l,node + r + 1,cmpy);
            return ;
        }
        int mid = (l + r) >> 1;
        ll midx = node[mid].x;
        Blocking(l,mid); Blocking(mid + 1,r);
        merge_node(l,mid,r);
        vector<Node> Q;
        for(int i = l; i <= r; i ++)
        {
            if((node[i].x - (midx)) * (node[i].x - (midx)) >= minx) continue;
            for(int j = Q.size() - 1; j >= 0; j --)
            {
                if((Q[j].y - (node[i].y)) *(Q[j].y - (node[i].y)) >= minx) break;
                dist_minx(Q[j],node[i]);
            }
            Q.push_back(node[i]);
        }
        Q.clear();
        return ;
    }
     
    int main()
    {
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        scanf("%d",&n);
        int top = 0;
        for(int i = 1; i <= n; i ++)
        {
            ll x,y;
            scanf("%lld%lld",&x,&y);
     
            node[++ top].x = x; node[top].y = y; node[top].id = i; node[top].stae = 1;
            node[++ top].x = -x; node[top].y = y; node[top].id = i;node[top].stae = 2;
            node[++ top].x = x; node[top].y = -y; node[top].id = i; node[top].stae = 3;
            node[++ top].x = -x; node[top].y = -y; node[top].id = i; node[top].stae = 4;
        }
        n = n * 4;
        sort(node + 1,node + n + 1,cmpx);
        Blocking(1,n);
        printf("%d %d %d %d\n",v1,s1,v2,5 - s2);
    }