HDU 4932 Miaomiao's Geometry

题目链接

题意：给定x轴上一些点（不重复），现在要选一个线段，使得能放进这些区间中，保证线段不跨过点（即线段上只能是最左边或最右边是点），并且没有线段相交，求能放进去的最大线段

思路：推理一下，只有两点之间的线段，还有线段的一半可能符合题意，然后对于每种线段，去判断一下能不能成功放进去，这步用贪心，优先放左边，不行再放右边

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 55; const double eps = 1e-9; int t, n; double a[N]; bool notless(double a, double b) { if (fabs(a - b) < eps) return true; return a > b; } bool judge(double len) { int flag = 1; for (int i = 2; i < n; i++) { if (flag && notless(a[i] - a[i - 1], len)) continue; else if (flag && a[i] - a[i - 1] < len && notless(a[i + 1] - a[i], len * 2)) continue; else if (flag && a[i] - a[i - 1] < len && notless(a[i + 1] - a[i], len)) { if (fabs(a[i + 1] - a[i] - len) >= eps) flag = 0; continue; } else if (!flag && notless(a[i + 1] - a[i], len * 2)) { flag = 1; continue; } else if (!flag && notless(a[i + 1] - a[i], len)) { if (fabs(a[i + 1] - a[i] - len) < eps) flag = 1; continue; } return false; } return true; } int main() { scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lf", &a[i]); sort(a + 1, a + 1 + n); double ans = 0; for (int i = 1; i < n; i++) { double len = a[i + 1] - a[i]; if (judge(len)) ans = max(ans, len); len /= 2; if (judge(len)) ans = max(ans, len); } printf("%.3lf\n", ans); } return 0; }