最近点对。

　　做法是先对所有点先按x再按y排序，然后进行分治搜索最近点对。对于每个区间，如果点数小于3，就直接暴力搜索最近点，否则对其进行分治。分治出来的两个区间，我们要挑选出与中点距离小于已找到的最近距离的所有点，然后对他们进行暴力枚举最近距离。根据《算法导论》证明的，合并两个区间之后，被挑选出来的点不会超过6个，于是可以得到总的时间复杂度是O(nlogn)。

代码如下：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 const int N = 111111;10 const double FINF = 1e100;11 12 template 
           
             T sqr(T x) { return x * x;}13 struct Point {14 double x, y;15 Point() {}16 Point(int x, int y) : x(x), y(y) {}17 bool operator < (Point a) const {18 return x < a.x || x == a.x && y < a.y;19 }20 Point operator + (Point a) {21 return Point(x + a.x, y + a.y);22 }23 } p[N];24 25 bool cmpY(int x, int y) { return p[x].y < p[y].y;}26 inline double dist(Point x, Point y) { return sqrt(sqr(x.x - y.x) + sqr(x.y - y.y));}27 28 #define lson l, m29 #define rson m + 1, r30 31 int arr[N];32 33 double closest(int l, int r) {34 if (l >= r) return FINF;35 if (l + 1 == r) return dist(p[l], p[r]);36 int m = l + r >> 1;37 double cd = min(closest(lson), closest(rson));38 int end = 0;39 for (int i = l; i <= r; i++) {40 if (dist(p[i], p[m]) <= cd) {41 arr[end++] = i;42 }43 }44 sort(arr, arr + end, cmpY);45 for (int i = 0; i < end; i++) {46 for (int j = i + 1; j < end; j++) {47 cd = min(cd, dist(p[arr[i]], p[arr[j]]));48 }49 }50 return cd;51 }52 53 int main() {54 // freopen("in", "r", stdin);55 int n;56 while (~scanf("%d", &n) && n) {57 for (int i = 0; i < n; i++) {58 scanf("%lf%lf", &p[i].x, &p[i].y);59 }60 sort(p, p + n);61 printf("%.2f\n", closest(0, n - 1) / 2.0);62 }63 return 0;64 }
           
          
         
        
       
      

 

UPD：

　　之前的代码估计是水过了，更新一下代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6  7 using namespace std; 8  9 template
           
             T sqr(T x) { return x * x;}10 typedef pair
            
              Point;11 #define x first12 #define y second13 inline double dist(Point a, Point b) { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}14 inline bool cmpx(Point a, Point b) { return a.x < b.x;}15 inline bool cmpy(Point a, Point b) { return a.y < b.y;}16 const int N = 111111;17 const double FINF = 1e100;18 19 #define lson l, m20 #define rson m + 1, r21 Point pt[N], tmp[N];22 23 double npp(int l, int r) {24 if (r - l <= 3) {25 double ret = FINF;26 for (int i = l; i < r; i++) {27 for (int j = i + 1; j <= r; j++) {28 ret = min(ret, dist(pt[i], pt[j]));29 }30 }31 return ret;32 }33 int m = l + r >> 1;34 Point mid = pt[m];35 double md = min(npp(lson), npp(rson));36 int tt = 0;37 for (int i = l; i <= r; i++) if (fabs(pt[i].x - mid.x) <= md) tmp[tt++] = pt[i];38 sort(tmp, tmp + tt, cmpy);39 for (int i = 0; i < tt; i++) {40 int j = i + 1;41 while (j < tt) {42 if (tmp[j].y - tmp[i].y > md) break;43 md = min(md, dist(tmp[i], tmp[j]));44 j++;45 }46 }47 return md;48 }49 50 int main() {51 //freopen("in", "r", stdin);52 int n;53 while (~scanf("%d", &n) && n) {54 for (int i = 0; i < n; i++) scanf("%lf%lf", &pt[i].x, &pt[i].y);55 sort(pt, pt + n, cmpx);56 printf("%.2f\n", npp(0, n - 1) / 2);57 }58 return 0;59 }
            
           
          
         
        
       
      

 

——written by Lyon