最接近点对问题
问题描述解题思路及所选算法策略的可行性分析伪代码描述及复杂度分析时间复杂度：部分代码
问题描述
给定平面上n个点，找出其中的一对点，它们之间的距离最小。
解题思路及所选算法策略的可行性分析
先选定一个点，再与其他n-1个点求出距离。找出最小的两点。这样效率太低需要O(n2)计算时间。计算时间下界为(nlogn)，可以采用分治法解决此问题。将n个点分成两个n/2个点的集合，再递归求最接近点。最后合并结果。经过分析，不论是一维，还是二维点，合并步可以在O(n)，时间内完成。
伪代码描述及复杂度分析
寻找S中各点x坐标的中位数赋值为m，构造S1和S2 两个集合递归求解接近点d1=cpair2(S1),d2=cpair2(S2)dm=min{d1,d2}；P1是S1中距垂直分割线L距离在dm之内的所有点组合集合 同理，P2是S2中的点集合 将P1,P2依照y坐标排序，X，Y为已排好序的点通过扫描X，检查每个点在Y中距离在dm之内的所有点完成合并（最多六个点）设dl是找到的最小距离d = min(dl,dm) Return d
时间复杂度：
1步，5步：O(n) 3步,6步：常数时间
T(n)=O（1） n<4 T(n)=2T(n/2)+O(n) n>=4
部分代码
public static class MergeSort{
public static void mergeSort(Comparable a
[]){
Comparable b
[] = new Comparable[a
.length
];
int s
= 1;
while(s
< a
.length
){
mergePass(a
,b
,s
);
s
+= s
;
mergePass(b
,a
,s
);
s
+= s
;
}
}
public static void mergePass(Comparable x
[],Comparable y
[],int s
){
int i
= 0;
while(i
<= x
.length
- 2 * s
){
merge(x
,y
,i
,i
+ s
- 1,i
+ 2 * s
- 1);
i
= i
+ 2 * s
;
}
if(i
+ s
< x
.length
)
merge(x
,y
,i
,i
+ s
- 1,x
.length
- 1);
else
for(int j
= i
;j
< x
.length
;j
++)
y
[j
] = x
[j
];
}
public static void merge(Comparable c
[],Comparable d
[],int l
,int m
,int r
){
int i
= l
,j
= m
+ 1,k
= l
;
while((i
<= m
) && (j
<= r
))
if(c
[i
].compareTo(c
[j
]) <= 0){
d
[k
++] = c
[i
++];
}
else
d
[k
++] = c
[j
++];
if(i
> m
)
for(int q
= j
;q
<= r
;q
++)
d
[k
++] = c
[q
];
else
for(int q
= i
;q
<= m
;q
++)
d
[k
++] = c
[q
];
}
}
public static class Point{
double x
,y
;
public Point(double xx
,double yy
){
x
= xx
;
y
= yy
;
}
}
public static class Point1 extends Point implements Comparable{
int id
;
public Point1(double xx
,double yy
,int theID
){
super(xx
,yy
);
id
= theID
;
}
public int compareTo(Object x
){
double xx
= ((Point1
)x
).x
;
if(this.x
< xx
)return -1;
if(this.x
== xx
)return 0;
return 1;
}
public boolean equals(Object x
){
return this.x
== ((Point1
)x
).x
;
}
public void getID(){
System
.out
.println(id
);
}
}
public static class Point2 extends Point implements Comparable{
int p
;
public Point2(double xx
,double yy
,int pp
){
super(xx
,yy
);
p
= pp
;
}
public int compareTo(Object x
){
double xy
= ((Point2
)x
).y
;
if(this.y
< xy
)
return -1;
if(this.y
== xy
)
return 0;
return 1;
}
public boolean equals(Object x
){
return this.y
== ((Point2
)x
).y
;
}
public void getp(){
System
.out
.println(p
);
}
}
public static class Pair{
Point1 a
;
Point1 b
;
double dist
;
public Pair(Point1 aa
,Point1 bb
,double dd
){
a
= aa
;
b
= bb
;
dist
= dd
;
}
public void print(){
System
.out
.println("输出点a的序号：");
a
.getID();
System
.out
.println("输出点b的序号：");
b
.getID();
System
.out
.println("输出两点之间的距离:");
System
.out
.println(dist
);
}
}
public static double dist(Point u
,Point v
){
double dx
= u
.x
- v
.x
;
double dy
= u
.y
- v
.y
;
return Math
.sqrt(dx
* dx
+ dy
* dy
);
}
public static Pair
cpair2(Point1 x
[]){
if(x
.length
< 2)
return null
;
MergeSort
.mergeSort(x
);
Point2 y
[] = new Point2[x
.length
];
for(int i
=0;i
< x
.length
;i
++)
y
[i
] = new Point2(x
[i
].x
,x
[i
].y
,i
);
MergeSort
.mergeSort(y
);
Point2 z
[] = new Point2[x
.length
];
return closestPair(x
,y
,z
,0,x
.length
- 1);
}
private static Pair
closestPair(Point1 x
[],Point2 y
[],Point2 z
[],int l
,int r
){
if(r
- l
== 1)
return new Pair(x
[l
],x
[r
],dist(x
[l
],x
[r
]));
if(r
- l
== 2){
double d1
= dist(x
[l
],x
[l
+ 1]);
double d2
= dist(x
[l
+ 1],x
[r
]);
double d3
= dist(x
[l
],x
[r
]);
if(d1
<= d2
&& d1
<= d3
)
return new Pair(x
[l
],x
[l
+ 1],d1
);
if(d2
<= d3
)
return new Pair(x
[l
+ 1],x
[r
],d2
);
else
return new Pair(x
[l
],x
[r
],d3
);
}
int m
= (l
+ r
) / 2;
int f
= l
,g
= m
+ 1;
for(int i
= l
;i
<= r
;i
++)
if(y
[i
].p
> m
)
z
[g
++] = y
[i
];
else z
[f
++] = y
[i
];
Pair best
= closestPair(x
,z
,y
,l
,m
);
Pair right
= closestPair(x
,z
,y
,m
+ 1,r
);
if(right
.dist
< best
.dist
)
best
= right
;
MergeSort
.merge(z
,y
,l
,m
,r
);
int k
= l
;
for(int i
= l
;i
<= r
;i
++)
if(Math
.abs(x
[m
].x
- y
[i
].x
) < best
.dist
)
z
[k
++] = y
[i
];
for(int i
= l
;i
< k
;i
++){
for(int j
= i
+ 1;j
< k
&& z
[j
].y
- z
[i
].y
< best
.dist
;j
++){
double dp
= dist(z
[i
],z
[j
]);
if(dp
< best
.dist
)
best
= new Pair(x
[z
[i
].p
],x
[z
[j
].p
],dp
);
}
}
return best
;
}
