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;

}

版权声明：本文博客原创文章，博客，未经同意，不得转载。