#include <cstdio>#include <iostream>#include <algorithm>#include <cmath>using namespace std;#define INF 100000000int n;struct point{double x,y;bool operator < (const point & a)const{if(a.x == x){return y < a.y;}else{return x < a.x;}}};int tmp[100005];point p[100005];int cmp(int a,int b){return p[a].y < p[b].y;}double dfun(point& a,point& b){return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)* (a.y-b.y);}/*最接近点对问题，的解法是利用分治的思想，，先将所有的点进行排序。拍完序之后所有的点分为左右两边选相等的两部分s1,s2因为这时候存在的最接近的点对就在s1和s2中，或者一点在s1一个点在s2很明显当一个点在s1一个点在s2中的时候有这两个点之间的距离到中间点的距离绝对不会超过d= min（s1,s2）;因为如果超过了中间点的距离那么他们之间的距离必然会大于d所以现在只需要枚举一下到中间点的距离小于d的点之间的距离就行了两边点已经求出来了最小的距离，这时候在中间点两边小于d的点就很少了，所以这时候就能做到优化 */ double close_pair(int l,int r){if(l >= r){return INF;}else if(l == r – 1){return dfun(p[l],p[r]);}else{int mid = l+(r-l)/2;double d1 = close_pair(l,mid);double d2 = close_pair(mid+1,r);double d = min(d1,d2);int k = 0;for(int i = l;i <= r ;i++){if( abs(p[i].y-p[mid].y) < d){tmp[k++] = i;}}sort(tmp,tmp+k,cmp);for(int i = 0;i < k;i++){for(int j = i+1;j < k;j++){if(dfun(p[tmp[i]],p[tmp[j]]) < d){d = dfun(p[tmp[i]],p[tmp[j]]);}}}return d;}}int main(){while(cin >> n,n){for(int i = 0;i < n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}sort(p,p+n);printf("%.2f\n",sqrt(close_pair(0,n-1))/2);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
世上没有绝望的处境，只有对处境绝望的人。
