两点之间的最近距离（不相交集） [英] Closest distance between two points(disjoint set)
问题描述
此问题是一种最接近对两个不相交集之间的。 上侧画面pssed这个问题EX $ P $。有两种不相交集，蓝色小点在-x平面上，红点在+ x平面的。
我要计算最小距离（距离| Y2，Y1 | + | X2 - X1 |）之间的一个蓝色圆点和一个红点，我觉得使用二进制搜索查找距离。如何使用二进制搜索这样的问题？ 我挣扎的唯一的 EX pressing二进制搜索两个不相交集。 我已经知道了一组，但我不知道的情况下两个分离的事。
++）它可以以线性时间使用Delaunay三角？ （才对啊，这是我的好奇心，我想用二进制搜索）
低于code，我已经编码一组的情况下（使用解决问题的方法，分而qonquer）和coverting两个不相交集。我不明白怎么做两套。 例如，提示。好吧..请帮助我的人？
的#include＆LT;的iostream＆GT;
＃包括＆LT;算法＆GT;
＃包括＆LT;了iomanip＆GT;
＃包括＆LT; CMATH＆GT;
/ **
测试输入
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
** /
使用名字空间std;
const int的MAX = 10001;
结构点{
INT X，Y;
};
布尔xCompare（结构来看，结构点）;
布尔yCompare（结构来看，结构点）;
INT DIS（结构来看，结构点）;
INT ABSD（INT）;
INT跟踪（INT，INT，INT，INT）;
点p [MAX] Q [MAX]，TMP [MAX]
诠释的main（）{
INT离开;
诠释权;
scanf函数（％D \ N，和放大器;左）;
memset的（对，0，sizeof的（P））;
memset的（Q，0，sizeof的（Q））;
memset的（TMP，0，sizeof的（TMP））;
的for（int i = 0; I＆LT;左;我++）{
CIN＆GT;＆GT; P [I] .X＆GT;＆GT; P [I] .Y;
}
scanf函数（％D \ N，和放大器;右一）;
对于（INT J = 0; J＆LT;权; J ++）{
CIN＆GT;＆GT; Q [J] .X＆GT;＆GT; Q [J] .Y;
}
排序（P，P +左，xCompare）;
排序（Q，Q +吧，xCompare）;
INT分钟=跟踪（0,0，左1，右1）;
的printf（％D \ N，分）;
/ **这是一组情况。
而（真）{
CIN＆GT;＆GT; N;
如果（N == 0）打破;
memset的（对，0，sizeof的（P））;
memset的（TMP，0，sizeof的（TMP））;
的for（int i = 0;我n种;我++）
CIN＆GT;＆GT; P [I] .X＆GT;＆GT; P [I] .Y;
排序（P，P + N，xCompare）;
INT分钟=微量（0，N-1）;
如果（分钟＆lt; 10000＆安培;＆安培; N大于1）{
COUT＆LT;＆LT;固定;
COUT＆LT;＆LT;集precision（4）＆LT;＆LT;分钟＆lt;＆其中; ENDL;
}
其他
COUT＆LT;＆LT; 无穷大＆LT;＆LT; ENDL;
}
** /
返回0;
}
INT跟踪（INT LOW1，诠释LOW2，诠释HIGH1，诠释HIGH2）{
如果（高温1 - 低温1 3;）{
int值= DIS（P [低温1]，Q [LOW2 + 1]）;
INT nextValue;
如果（高温1 - LOW1 == 2）{
nextValue = DIS（P [低温1]，Q [LOW2 + 2]）;
如果（值GT; nextValue）
值= nextValue;
nextValue = DIS（对[LOW1 + 1]，则q [LOW2 +2]）;
如果（值GT; nextValue）
值= nextValue;
}
返回值;
}
其他{
/ *分割和放大器; QONQUER * /
INT MID1 =（低温1 +高温1）＆GT;＆GT; 1;
INT MID2 =（LOW2 + HIGH2）＆GT;＆GT; 1;
INT CNT = 0;
INT leftValue =跟踪（LOW1，LOW2，MID1，MID2）; //左跟踪
INT rightValue =跟踪（MID1 + 1，MID2 + 1，高温1，高温2）; //正确跟踪
//最小值找到
int值= leftValue＆LT; rightValue？ leftValue：rightValue;
/ *中条件检查：Y行* /
//节省左
的for（int i =低温1; I＆LT; = MID1;我++）{
如果（ABS（P [I] .X - Q [MID2] .X）＆LT; =值）
TMP [CNT ++] = P [i];
}
//节省权
的for（int i = MID1 + 1; I＆LT; =高温1;我++）{
如果（ABSD（P [I] .X - Q [MID2 + 1] .X）＆LT; =值）
TMP [CNT ++] = P [i];
}
排序（TMP，TMP + CNT，yCompare）;
的for（int i = 0; I＆LT; CNT;我++）{
诠释计数= 0;
为（中间体J =-3;计数＆10 6安培;＆安培; J＆所述; CNT; J ++）{
如果（J＆GT; = 0＆功放;＆安培;！I = j）条{
INT距离= DIS（TMP [我]，TMP [J]）;
如果（值GT;距离）
值=距离;
算上++;
}
}
}
返回值;
}
}
INT ABSD（INT X）{
如果（X℃，）
返回-x;
返回X;
}
诠释DIS（结构点，结构点b）{
返程（ABS（a.x-b.x）+ ABS（a.y-b.y））;
}
布尔xCompare（结构点了，结构点b）{
返回a.x＆LT; b.x;
}
布尔yCompare（结构点了，结构点b）{
返回a.y＆LT;通过;
}
这个问题通常被称为最近双色对问题。这里有几个方法。
-
Delaunay三角。 （这当然与L-作品 2 （=欧几里德）距离。我认为步骤概括为L <子> 1 ）对于每一个Delaunay三角（可以有超过三分之一的退化例），存在一个最小生成树其边缘都属于三角测量。反过来，这种最小生成树包含最短边渡色类之间的切换。
-
最近邻居的数据结构。
-
如果它被赋予了红点从蓝点分离X，那么你可能能够适应的O（n）的合并Shamos - 霍伊分而治之算法的步骤最接近（单色）对问题，说明这里 。
This problem is a kind of closest pair between two disjoint set. Upperside picture is expressed this problem. there is two kind of disjoint set, blue dots in -x plane, red dots in +x plane.
I want to calculate minimum distance(distance is |y2-y1| + |x2 - x1|) between one blue dot and one red dot, and I think use binary search for finding distance. How to use binary search this kind of problem? I struggle on only expressing binary search two disjoint sets. I have already know for one set, but I don't know in case two disjoint sets.
++ ) it is can in linear time using Delaunay triangulation? (ah, it is only my curiosity, I want to use binary search)
below code which I had already coding one set case(using problem-solving technique, divide and qonquer) and coverting to two disjoint set. I don't understand how to do in two sets. Example, Hint. okay.. please someone help me?
#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;
}
This problem is usually called the closest bichromatic pair problem. Here are a couple approaches.
Delaunay triangulation. (This certainly works with L2 (= Euclidean) distances; I think the steps generalize to L1.) For every Delaunay triangulation (there can be more than one in degenerate cases), there exists a minimum spanning tree whose edges all belong to the triangulation. In turn, this minimum spanning tree contains a shortest edge crossing the cut between the color classes.
Nearest neighbor data structures.
If it is given that the red points are separated in x from the blue points, then you may be able to adapt the O(n) merge step of the Shamos–Hoey divide-and-conquer algorithm for the closest (monochromatic) pair problem, described here.
这篇关于两点之间的最近距离（不相交集）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
