本文主要是介绍HDU 4932 Miaomiao's Geometry（推理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 4932 Miaomiao's Geometry
题目链接
题意：给定x轴上一些点（不重复），现在要选一个线段，使得能放进这些区间中，保证线段不跨过点（即线段上只能是最左边或最右边是点），并且没有线段相交，求能放进去的最大线段
思路：推理一下，只有两点之间的线段，还有线段的一半可能符合题意，然后对于每种线段，去判断一下能不能成功放进去，这步用贪心，优先放左边，不行再放右边
代码：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
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;
}这篇关于HDU 4932 Miaomiao's Geometry（推理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
