记录编号	577660	评测结果	AWAWAAAAWA
题目名称	[USACO Jan16]愤怒的奶牛	最终得分	70
用户昵称	yrtiop	是否通过	未通过
代码语言	C++	运行时间	1.165 s
提交时间	2022-11-20 12:45:23	内存使用	4.81 MiB

#include <bits/stdc++.h>

const double eps = 1e-3;
const int maxn = 5e4 + 5;
int n;
double a[maxn],pre[maxn],suf[maxn];

bool check(double k) {
	for(int i = 1;i <= n;++ i) {
		int r = std::upper_bound(a + 1 , a + 1 + n , a[i] + 2.0 * k) - a - 1;
		if(pre[i] <= k - 1&&suf[r] <= k - 1)return true;
	}
	for(int i = n;i;-- i) {
		int r = std::lower_bound(a + 1 , a + 1 + n , a[i] - 2.0 * k) - a;
		if(pre[r] <= k - 1&&suf[i] <= k - 1)return true;
	}
	return false;
}

int main() {
	freopen("angry.in","r",stdin);
	freopen("angry.out","w",stdout);
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i)
		scanf("%lf",&a[i]);
	std::sort(a + 1 , a + 1 + n);
	pre[1] = 0;
	for(int i = 2;i <= n;++ i) {
		pre[i] = 1e9;
		double l = a[i] - a[i - 1],r = 1e9;
		while(r - l > eps) {
			double mid = (l + r) / 2.0;
			int k = std::lower_bound(a + 1 , a + 1 + n , a[i] - mid) - a;
			if(pre[k] <= mid - 1)r = mid;
			else l = mid;
		}
		pre[i] = r;
	}
	suf[n] = 0;
	for(int i = n - 1;i;-- i) {
		suf[i] = 1e9;
		double l = a[i + 1] - a[i],r = 1e9;
		while(r - l > eps) {
			double mid = (l + r) / 2.0;
			int k = std::upper_bound(a + 1 , a + 1 + n , a[i] + mid) - a - 1;
			if(suf[k] <= mid - 1)r = mid;
			else l = mid;
		}
		suf[i] = r;
	}
	double l = 0,r = 1e9;
	while((r - l) > eps) {
		double mid = (l + r) / 2.0;
		if(check(mid))r = mid;
		else l = mid;
	} 
	printf("%.1lf\n",l);
	return 0;
}