题目大意:
给定一堆点集，在这一堆点集中找到一组点集它们之间的距离达到最短
对于HDU1007因为求圆的半径，所以距离还要除以2
普通情况下，可以将nge点，将任意两个点之间的距离都算一遍，在循环过程中，每次取到距离的较小值
但数据量大的话，这种O（n^2）的方法肯定是不合理的
转化为O（nlogn)的方法是可取的
这里采用分治的方法
我们希望尽可能的均匀分配，也就是让左右两端所含有的点的数目一样多，所以一开始就根据以x优先排序 ， 然后取中值作为分割边
int fenzhi(int l , int r)
{
int m = (l+r) >> 1;
int d1 = fenzhi(l , m);
int d2 = fenzhi(m+1 , r);
int d3 = 左右两部分的点相互作距离运算得到 //也就是一个合并的过程
return min(d1 , d2 , d3);
}
当l == r时 无疑距离不存在，我们返回一个最大值maxn即可不会影响结果
当l == r-1说明只存在两个点， 那就是将这两个点的距离作为最短距离返回即可
由于是自底向下
我们可以根据d1 ， d2 ， 优先得到d = min(d1 , d2)
那样我们在合并的过程中只要找距离小于d的点就可以了，我们不能将所有点都访问一遍，但是我们可以控制一个范围
先找到所有离分割线距离小于d的点，也即左侧的图所示，超出那个范围的话必然左右两个点相连距离大于d
找到所有符合点将其下标用rec数组保存即可
然后将rec数组中的点全都比较一遍，比较过程中可以先只关注两点在y轴上的距离是否小于d ， 是的话计算距离，并且与原距离取最小值
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 #define N 100005 8 #define maxn 2000000000 9 10 struct Point{ 11 double x , y; 12 //利用减法运算计算两点间的距离 13 double operator-(const Point &m)const{ 14 return sqrt((x-m.x)*(x-m.x) + (y-m.y)*(y-m.y)); 15 } 16 }p[N]; 17 18 bool cmpxy(const Point &m1 , const Point &m2){ 19 if(m1.x == m2.x) return m1.y < m2.y; 20 return m1.x < m2.x; 21 } 22 23 //d要随之更改，所以参数要引用传递 24 void merge_l_r(double &d , int l , int r) 25 { 26 int m = (l+r) >> 1; 27 /*得到所有离分割线距离不大于d的点，否则本身到分割线就大于d，那么左右两侧相连必然大于d 28 就没有保留下去的必要了*/ 29 int rec[N] , k = 0;//记录所有符合点的编号 30 for(int i = l ; i<=r ; i++){ 31 if(p[m] - p[i] < d) 32 rec[k++] = i; 33 } 34 35 //有见到别人博客在这里将rec根据对应点的y的大小排了一次序，但我提交了好像时间反而更长就干脆不用了 36 /* 37 大致如下： 38 现在最外面写个 39 bool cmpxy(const Point &m1 , const Point &m2){ 40 if(m1.x == m2.x) return m1.y < m2.y; 41 return m1.x < m2.x; 42 } 43 这个位置写个sort(rec , rec+k , cmpy); 44 */ 45 for(int i=0 ; i<k ; i++){ 46 for(int j=i+1 ; j<k ; j++){ 47 if(abs(p[rec[j]].y - p[rec[i]].y) < d) 48 d = min(d , p[rec[j]] - p[rec[i]]); 49 } 50 } 51 } 52 53 double fenzhi(int l , int r) 54 { 55 int m = (l+r) >> 1; 56 //这里是计算两点的最短距离，l==r只有一个点存在，所以输出一个最大距离使其不影响结果 57 if(l == r) return maxn; 58 if(l == r-1) return p[l] - p[r]; 59 60 double d; 61 //处理左边 62 double d1 = fenzhi(l , m); 63 //处理右边 64 double d2 = fenzhi(m+1 , r); 65 //得到左右两部分中两点间的最小值 66 d = min(d1 , d2); 67 68 //将这个最小值和左右两部分的点相连得到的最小边作比较 69 merge_l_r(d , l , r); 70 71 return d; 72 } 73 74 int main() 75 { 76 int n; 77 while(scanf("%d" , &n) , n){ 78 for(int i = 0 ; i<n ; i++){ 79 scanf("%lf%lf" , &p[i].x , &p[i].y); 80 } 81 sort(p , p+n , cmpxy); 82 //这里是取圆的半径所以除以二 83 printf("%.2f " , fenzhi(0 , n-1) / 2); 84 } 85 return 0; 86 }