首页 > 代码库 > HDU 4932 Miaomiao's Geometry(推理)
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。