java最接近对点及距离_最接近点对问题_分治法
⼀、问题描述
给定平⾯上的n个点，找其中的⼀对点，使得在n个点组成的所有点对中该点对间的距离最⼩。
⼆、解题思路及所选算法策略的可⾏性分析
思路：利⽤分治法来解决问题。递归⼦结构求最接近点对总体可分为⼏个步骤：
1、当问题规模⼩于20，直接求解最⼩点对
2、将n个点组成的集合S分成2个⼦集S1和S2
3、递归求出两个⼦集中的最接近点对并⽐较出最⼩点对，记录距离dmin
4、以X坐标为基准找到所有点中线，在中线附近找出相距可能⼩于dmin的点对点，记录于S3和S4
5、求S3和S4每点对距离，和dmin进⾏⽐较，求解最接近点对
策略可⾏性分析：
设直线l上有2m个点，以m为中点将l分割成两条线段dl,dr，然后求出dl和dr这两点条线段中的最⼩点距d1,d2，此时d=min{d1,d2}，再通过计算出dl线段的中最⼤点与dr线段中的最⼩点之间的距离D，最⼩距离则为min{d,D}.
⼆维情况与此相似，最⼤的区别只是对于中线位置的点，⼆维情况只是针对中线旁好多可能点，再在Y轴⽅向上进⾏点的筛选，以减少平⽅计算次数。
三、伪代码描述及复杂度分析
Public static double clostPoint(S)
{
1、⾸先，递归结束条件，当数组长度在⼀定范围内时直接求出最近点，蛮⼒求解
2、求所有点在X坐标中的中位数midX
3、以midX为界将所有点分成两组分别存放在两个表中
4、将两张表转化为数组类型，并分别按X坐标升序排列
5、求S1中的最近距离的两个点
6、求S2中的最近距离的两个点
幼儿电影7、求两最近距离的最⼩值
8、在S1、S2中收集距离中线⼩于d1的点，分别存放于两个表中
9、分别将表T3、T4转换为数组类型的S3、S4，并将其分别按Y坐标升序排列
10、求解S3、S4两者之间可能的更近(相⽐于d1)距离 , 以及构成该距离的点
}
复杂度分析：
设算法耗时T(n)。 算法第1步、第2步、第3步和第8步⽤了O(n)时间。第7步和第10步⽤了常数时间。第4步和第9步⽤了O(nlogn)时间。第5步和第6步分别⽤了T(n/2)时间。不过第4步和第9步是数组的排序预处理时间，所以不算在算法中。所以经由预处理的算法所需计算时间满⾜递归⽅程：
变化英语
T(n)={ O(1) n<4
2T(n/2)+O(n) n>=4
由此，T(n)=O(nlogn)。
代码实现
dcPoint.java
package 分治法;
public class dcPoint implements Cloneable, Comparable{ public dcPoint() {
x = 0;
y = 0;
}如何做红烧鱼
public dcPoint(int x, int y) {
this.x = x;
this.y = y;
属狗人的性格}
public void tX(int x) {
this.x = x;
}
public void tY(int y) {
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
private int x;
private int y;
@Override
public int compareTo(dcPoint o) {
if(x == o.getX() && y == o.getY())
爱心包裹
return 0;
el
return 1;
}
NPointPair.java
package 分治法;
import java.util.ArrayList;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;
public class NPointPair {
/**
* 最近点问题
* @param S
*/
public static dcPoint[] clostPoint(dcPoint [] S){
dcPoint[] result = new dcPoint[2];
/**
* 0.⾸先，解决该问题的边界，当数组长度在⼀定范围内时直接求出最近点，蛮⼒求解
*/
double dmin = Double.POSITIVE_INFINITY;
double tmpmin = 0;
if(S.length <= 20){
for(int i = 0; i < S.length; i ++){
for(int j = i + 1; j < S.length; j ++){
tmpmin = Math.sqrt(Math.pow(S[i].getX() - S[j].getX(), 2)) + Math.pow(S[i].getY() - S[j].getY(), 2); if(tmpmin < dmin){
dmin = tmpmin;
result[0] = S[i];
result[1] = S[j];
}
}
}
return result;
简介怎么写}
/**
*1.求所有点在X坐标的中位数
int minX = (int) Double.POSITIVE_INFINITY;//保证假设的初始最⼩值⾜够⼤int maxX = (int) Double.NEGATIVE_INFINITY;//保证假设的初始最⼤值⾜够⼩for(int i = 0; i < S.length; i++){隗嚣
if(S[i].getX() < minX)
minX = S[i].getX();
if(S[i].getX() > maxX)
maxX = S[i].getX();
}
int midX = (minX + maxX)/2;
/**
* 2.以midX为界将所有点分成两组分别存放在两个表中
*/
ArrayList T1 = new ArrayList();
ArrayList T2 = new ArrayList();
for(int i = 0; i < S.length; i++){
if(S[i].getX() <= midX)//是否要=号？
T1.add(S[i]);
if(S[i].getX() > midX)
T2.add(S[i]);
}
/**
* 3.将两张表转化为数组类型，并分别按X坐标升序排列
*/
dcPoint [] S1 = new dcPoint[T1.size()];
dcPoint [] S2 = new dcPoint[T2.size()];
mergeSort(S1, "x");//按X坐标升序排列
mergeSort(S2, "x");//按X坐标升序排列
/**
* 4.求S1中的最近距离的两个点
*/
dcPoint[] result1 = new dcPoint[2];
result1 = clostPoint(S1);
/**
* 5.求S2中的最近距离的两个点
*/
dcPoint[] result2 = new dcPoint[2];
result2 = clostPoint(S2);
/**
* 6.求两最近距离的最⼩值
*/
double d1 = Math.sqrt(Math.min(Math.pow(result1[0].getX() - result1[1].getX(), 2) + Math.pow(result1[0].getY() -result1[1].getY(), 2),五官歌儿歌
Math.pow(result2[0].getX() - result2[1].getX(), 2) + Math.pow(result2[0].getY() - result2[1].getY(), 2)));
if(Math.pow(result1[0].getX() - result1[1].getX(), 2) + Math.pow(result1[0].getY() - result1[1].getY(), 2) <
Math.pow(result2[0].getX() - result2[1].getX(), 2) + Math.pow(result2[0].getY() - result2[1].getY(), 2))
result = result1;
el
result = result2;
/**
* 7.在S1、S2中收集距离中线⼩于d1的点，分别存放于两个表中
*/
ArrayList T3 = new ArrayList();
ArrayList T4 = new ArrayList();
for(int i = 0; i < S1.length; i++){
if(midX - S1[i].getX() < d1)
T3.add(S1[i]);
}
for(int i = 0; i < S2.length; i++){
if(S2[i].getX() - midX < d1){
T4.add(S2[i]);
}
}
/**
* 8.分别将表T3、T4转换为数组类型的S3、S4，并将其分别按Y坐标升序排列
*/
