HDU 4932 Miaomiao's Geometry（推理）

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;
}