c++ - 两点之间的最近距离(不相交集)

Question

这个问题是两个不相交集合之间的一种最近对。上图表示这个问题。有两种不相交的集合，-x 平面上的蓝点，+x 平面上的红点。

我想计算一个蓝点和一个红点之间的最小距离(距离是|y2-y1| + |x2 - x1|)，我认为使用二分法查找距离。如何使用二分查找这种问题？我只在表达二分搜索两个不相交的集合上苦苦挣扎。我已经知道一组，但我不知道是否有两个不相交的组。

++ ) 可以在线性时间内使用 Delaunay 三角剖分吗？ (啊，这只是我的好奇心，我想使用二进制搜索)

下面的代码我已经编写了一组案例(使用解决问题的技术，划分和 qonquer)并转换为两个不相交的集合。我不明白怎么做两套。例如，提示。好吧..有人帮帮我吗？

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>

/**
test input
10
-16 -4 
-1 -3 
-9 -1 
-4 -10 
-11 -6 
-20 4 
-13 6 
-3 -10 
-19 -1 
-12 -4
10
8 2
10 3 
10 10 
20 -3 
20 3 
16 2
3 -5 
14 -10
8 -2 
14 0

10
-3 39
-2 -28
-1 20
-3 11
-3 45
-2 -44
-1 -47
-5 -35
-5 -19
-5 -45
10
27 5
28 0
28 5
21 5
2 3
13 -1
16 -2
20 -2
33 -3
27 1
 **/


using namespace std;

const int MAX = 10001;

struct point{
    int x,y;
};

bool xCompare(struct point, struct point);
bool yCompare(struct point, struct point);
int dis(struct point, struct point);

int absd(int);
int trace(int,int,int,int);

point p[MAX], q[MAX], tmp[MAX];

int main(){

    int left;
    int right;

    scanf("%d\n", &left);
    memset(p,0,sizeof(p));
    memset(q,0,sizeof(q));
    memset(tmp,0,sizeof(tmp));


    for(int i=0; i<left; i++){
        cin >> p[i].x >> p[i].y;
    }

    scanf("%d\n", &right);

    for(int j=0; j<right; j++){
        cin >> q[j].x >> q[j].y;
    }

    sort(p, p+left, xCompare);
    sort(q, q+right, xCompare);

    int min = trace(0,0, left-1, right-1);

    printf("%d\n", min);


    /** this is one set case.
    while(true){
        cin >> n;

        if(n == 0)  break;

        memset(p,0,sizeof(p));
        memset(tmp,0,sizeof(tmp));

        for(int i= 0;i<n;i++)
            cin >> p[i].x >> p[i].y;

        sort(p,p+n,xCompare);

        int min = trace(0,n-1);

        if(min < 10000 && n > 1){
            cout << fixed;
            cout << setprecision(4) << min << endl;
        }
        else
            cout << "INFINITY" << endl;
    }
     **/

    return 0;
}

int trace(int low1, int low2, int high1, int high2){

    if(high1 - low1 < 3){
        int value = dis(p[low1],q[low2+1]);
        int nextValue;

        if(high1 - low1 == 2){  
            nextValue = dis(p[low1],q[low2+2]);

            if(value > nextValue)
                value = nextValue;

            nextValue = dis(p[low1+1],q[low2+2]);

            if(value > nextValue)
                value = nextValue;
        }
        return value;
    }
    else{

        /* DIVIDE & QONQUER */

        int mid1 = (low1 + high1) >> 1;
        int mid2 = (low2 + high2) >> 1;
        int cnt = 0;

        int leftValue = trace(low1,low2,mid1,mid2);     // left trace
        int rightValue = trace(mid1+1,mid2+1,high1,high2);  // right trace

        // min value find
        int value = leftValue < rightValue ? leftValue : rightValue;

        /* Middle Condition Check : Y Line */

        // saving left
        for(int i = low1;i<=mid1;i++){
            if(abs(p[i].x - q[mid2].x) <= value)
                tmp[cnt++] = p[i];
        }

        // saving right
        for(int i = mid1+1;i<=high1;i++){
            if(absd(p[i].x - q[mid2+1].x) <= value)
                tmp[cnt++] = p[i];
        }

        sort(tmp,tmp+cnt,yCompare);

        for(int i = 0;i<cnt;i++){
            int count = 0;

            for(int j = i-3;count < 6 && j < cnt;j++){
                if(j >= 0 && i != j){
                    int distance = dis(tmp[i],tmp[j]);

                    if(value > distance)
                        value = distance;

                    count++;
                }
            }
        }
        return value;
    }
}

int absd(int x){
    if( x < 0)
        return -x;
    return x;
}

int dis(struct point a, struct point b){
    return (abs(a.x-b.x) + abs(a.y-b.y));
}

bool xCompare(struct point a, struct point b){
    return a.x < b.x;
}

bool yCompare(struct point a, struct point b){
    return a.y < b.y;
}

Answer 1

这个问题通常被称为最近的双色对问题。这里有几种方法。

1. Delaunay 三角剖分。 (这当然适用于 L₂ (= Euclidean) 距离；我认为这些步骤可以推广到 L₁。)对于每个 Delaunay 三角剖分(退化的可能不止一个例)，存在一个最小生成树，其边都属于三角剖分。反过来，这个最小生成树包含一个最短边，穿过颜色类之间的切线。

2. 最近邻数据结构。

3. 如果给定 x 中的红点与蓝点分开，那么您可以将 Shamos–Hoey 分治算法的 O(n) 合并步骤用于最接近(单色)对问题，描述 here .