题目链接：hdu 4932 Miaomiao's Geometry

题目大意：在x坐标上又若干个点，现在要用若干条相等长度的线段覆盖这些点，若一个点被一条线段覆盖，则必须在这条线的左端点或者是右端点，并且各个线段放的位置不能又重叠，求最大长度。

解题思路：这题有坑点，比赛的时候o(n)的算法去寻找两点之间最短距离。但起始这样是不行的，比如-1 0 10 12 18 20，这样维护过去的话，最短应该是12~18，长度为6，这段线段可以覆盖12和18的点，然后-1和20又在两端。于是只有0和10两点，0和10之间的长度为10，大于6，所以一段不够，两端又有重叠。
赛后的做法，枚举两点之间的长度，以及长度的一半，判断是否可行，维护最大值。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 100; int n; double arr[maxn]; bool judge (double w) { double tmp = arr[0]; for (int i = 1; i < n; i++) { if (fabs(arr[i] - tmp) < 1e-9 || arr[i] - tmp > w || fabs(arr[i] - tmp - w) < 1e-9) tmp = arr[i]; else if (arr[i] < tmp) return false; else tmp = arr[i] + w; } return true; } int main () { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%lf", &arr[i]); sort(arr, arr + n); double ans = 0; for (int i = 1; i < n; i++) { if (judge (arr[i] - arr[i-1])) ans = max(ans, arr[i] - arr[i-1]); else if (judge((arr[i] - arr[i-1]) / 2)) ans = max(ans, (arr[i] - arr[i-1]) / 2); } printf("%.3lf\n", (double)ans); } return 0; }