首页 > 代码库 > 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;
}