记录编号	244480	评测结果	AAAAAAAAAA
题目名称	2204.[USACO Jan16]愤怒的奶牛	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	3.254 s
提交时间	2016-04-01 10:30:23	内存使用	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)
{
	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)
{
	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;
	}
	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)
{
	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);
	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;
}