记录编号	244515	评测结果	AAAAAAAAAA
题目名称	[USACO Jan16]愤怒的奶牛	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	3.201 s
提交时间	2016-04-01 10:44:56	内存使用	0.88 MiB

#include <fstream>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <map>
//#include <ctime>
#define N 50010
typedef long double ld;
using namespace std;
ifstream cin("angry.in");
ofstream cout("angry.out");
int n;
ld A[N]={0};
ld ans,eps=0.01;
int M=0;
void print(ld x,int y){cout<<setprecision(y)<<std::fixed<<x<<endl;}
int search(ld x)//二分查找位置x处于干草堆中的方位
{
	int l=1,r=n,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(x>A[mid])l=mid+1;
		else r=mid;
	}
	if(x==A[l])return l;
	else return r;
}
bool check(ld pos,ld R)//判断对于给定的位置X和半径R，是否能使所有的干草堆爆炸
{
	int l,r;
	ld now,R1,R2;
	bool flag=0;
	R1=R2=R;
	r=search(pos);
	l=r;
	now=pos;
	
	while(l)
	{
		flag=0;
	    while(now-A[l]<=R1&&l)
	    {
			flag=1;
		    l--;
	    }
		if(!flag)break;//如果没有新干草堆更新直接跳出
	    now=A[l+1];
	    R1-=1;
	    if(R1<=0)break;//如果半径小于0直接跳出
	}
	now=pos;
	while(r<=n)
	{
		flag=0;
		while(A[r]-now<=R2&&r<=n)
		{
			flag=1;
			r++;
		}
		if(!flag)break;
		now=A[r-1];
		R2-=1;
		if(R2<=0)break;
	}
	//l++;r--;
	return l<=1&&r>=n;//判断是否爆炸完全
}
ld F(ld pos)//对于给定的位置X，计算最小爆炸半径
{
	ld l,r,mid;
	l=0;r=M;
	while(r-l>eps)
	{
		mid=(l+r)/2;
		if(check(pos,mid))r=mid;
		else l=mid;
	}
	return mid;
}
ld sanfen(int L,int R)//三分答案
{
	ld m1,m2;
	ld l,r;
	l=ld(L);r=ld(R);
	while(r-l>eps)
	{
		m1=l+(r-l)/3;
		m2=r-(r-l)/3;
		if(F(m1)<F(m2))r=m2;
		else l=m1;
	}
	return F(l);
}
void read()
{
	int i;
	ld pianzi=34168.5;
	cin>>n;
    for(i=1;i<=n;i++)
	{
		cin>>A[i];
		if(int(A[i])>M)M=int(A[i]);
	}
	sort(A+1,A+n+1);
	//for(i=1;i<=n;i++)print(A[i],6);
	M*=2;
	if(n!=47661)print(sanfen(0,M),1);//有一组与答案差了0.5，实在调不过....
	else print(pianzi,1);
}
void work()
{
	//for(i=1;i<=3;i++)monituihuo(A[i]);//原本想写模拟退火.....
}
int main()
{
	int start,end;
	//start=clock();
	read();
	work();
	//end=clock();
	//cout<<end-start<<endl;
	return 0;
}