Ближайшее расстояние между двумя точками (disjoint set)

Эта задача представляет собой поиск ближайшей пары между двумя непересекающимися множествами. На рисунке вверху выражена эта задача. Есть два вида непересекающихся множеств, синие точки в плоскости -x, красные точки в плоскости +x.

Я хочу вычислить минимальное расстояние (расстояние |y2-y1| + |x2 - x1|) между одной синей точкой и одной красной точкой, и я думаю использовать бинарный поиск для нахождения расстояния. Как использовать двоичный поиск в такой задаче? Я борюсь только над выражением двоичного поиска двух непересекающихся множеств. Я уже знаю для одного множества, но не знаю в случае двух непересекающихся множеств.

++ ) это можно сделать за линейное время, используя триангуляцию Делоне? (ах, это только мое любопытство, я хочу использовать двоичный поиск)

ниже код, который я уже кодировал один случай множества (используя технику решения проблем, разделение и 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;
}