//圓排列的隨機(jī)化算法

#include <fstream.h>
#include <iostream.h>
#include <math.h>
#include <time.h>

//隨機(jī)數(shù)類

const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;

class RandomNumber{
public:
	RandomNumber(unsigned long s=0);  //構(gòu)造函數(shù)，缺省值0表示由系統(tǒng)自動(dòng)產(chǎn)生種子
	unsigned short Random(unsigned long n);  //產(chǎn)生0：n-1之間的隨機(jī)整數(shù)
	double fRandom(void); //產(chǎn)生[0,1)之間的隨機(jī)實(shí)數(shù)
private:
	unsigned long randSeed;
};

RandomNumber::RandomNumber(unsigned long s)
{
	if(s==0)
		randSeed=time(0);
	else 
		randSeed=s;
}

unsigned short RandomNumber::Random(unsigned long n)
{
	randSeed=multiplier*randSeed+adder;
	return(unsigned short)((randSeed>>16)%n);
}

double RandomNumber::fRandom(void)
{
	return Random(maxshort)/double(maxshort);
}

//交換函數(shù)
void Swap(float &x,float &y)
{
	float temp;
	temp=x;
	x=y;
	y=temp;
}
//圓排列類
class Circle{
	friend float CirclePerm(int,float*);//返回找到的最小圓排列長度
private:
	void Center(void);//計(jì)算當(dāng)前所有的圓在當(dāng)前圓排列中圓心的橫坐標(biāo)
	float Compute(void);//計(jì)算當(dāng)前圓排列的長度
	void Circle_Perm(void); //隨機(jī)排列算法
	void CircleSearch(void); //圓排列隨機(jī)算法

	float min,//當(dāng)前最優(yōu)值
		result, //最優(yōu)值
		*x,//當(dāng)前圓排列圓心橫坐標(biāo)
		*r;//當(dāng)前圓排列
	int n;//等排列圓的個(gè)數(shù)
};


void Circle::Center(void)
{
	for(int i=0;i<n;i++){
		float temp=0;
		for(int j=0;j<i;j++){
			float valuex=x[j]+(float)(2.0*sqrt(r[i]*r[j]));
			if(valuex>temp) temp=valuex;
		}
		x[i]=temp;
	}
}

float Circle::Compute(void)
{
	float low=0;
	float high=0;
	for(int i=0;i<n;i++){
		if(x[i]-r[i]<low) low=x[i]-r[i];
		if(x[i]+r[i]>high) high=x[i]+r[i];
	}	
	return (high-low);
}

void Circle::Circle_Perm(void)
{
	static RandomNumber rnd;
	
	for(int i=0;i<n;i++){
		int j=rnd.Random(n-i)+i;
		Swap(r[i],r[j]);
	}
}

void Circle::CircleSearch(void)
{
	Circle_Perm();
	Center();
	min=Compute();
	
	bool found=true;
	while(found){
		found=false;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++){
				Swap(r[i],r[j]);
				Center();
				float length=Compute();
				if(length<min){
					min=length;
					found=true;
				}
				else Swap(r[i],r[j]);
			}
	}
	
}		


float CirclePerm(int n,float* a)
{
	Circle X;
	X.n=n;
	X.r=a;
	
	float *x=new float[n];
	for(int i=0;i<n;i++) x[i]=0;
	X.x=x;
    X.CircleSearch();
	X.result=X.min;
   //重復(fù)50次	
   for(i=1;i<=50;i++){
		X.CircleSearch();
		if(X.result>X.min) {
			 X.result=X.min;
		}

	 }
	
	
   delete []x;
	return X.result;
}

int main(void)
{
	int n;
	float result;
	ifstream input;
	input.open("input.txt");
	input>>n;
	float *a=new float[n];
	for(int i=0;i<n;i++) input>>a[i];
	input.close();

	result=CirclePerm(n,a);	

	ofstream output;
	output.open("output.txt");
	output<<result;
	output.close();

	delete []a;
	return 0;
}