1-D closet pair 一维的最近点对

分治算法，每次比较左，右，和中间三个最近点对！

http://soj.sysu.edu.cn/show_problem.php?pid=1001&cid=1750

 Input:
 4
 1 3 6 10
 Output:
 2.000000

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const double eps = 1e-6;
 9 double a[1000005];
10 double res;
11 
12 void closest_path(int l, int r)
13 {
14     if(l == r)
15         return ;
16     if(l + 1 == r)
17     {
18         if(res > a[r]-a[l]+eps)
19             res = a[r]-a[l];
20     } 
21     int mid = (l + r) / 2;
22     if(res > a[mid+1]-a[mid]+eps) //还要判断中间相邻两个的差 
23         res = a[mid+1]-a[mid];
24     closest_path(mid+1, r);
25     closest_path(l, mid);
26 }
27 
28 int main()
29 {
30     int n;
31     while(scanf("%d", &n) != EOF)
32     {
33         res = 1000000;
34         for(int i=0; i<n; i++)
35             scanf("%lf", &a[i]);
36         sort(a, a+n);
37         closest_path(0, n-1);
38         printf("%.6lf
", res);
39     }
40     return 0;
41 }