Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include <iostream>
#include <cmath>
#include <cassert>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

double r[1010],x[1010];

const double eps=1e-5;
const double inf=1e9;

bool cross(int m,double cx,double cy){
	rep(i,m){
		double dd=0.0;
		dd+=1.0*(x[i]-cx)*(x[i]-cx);
		dd+=1.0*(r[i]-cy)*(r[i]-cy);
		double rr=1.0*(r[i]+r[m])*(r[i]+r[m]);
		// cerr << rr << " " << dd << endl;
		if(rr>dd+eps) return true;
	}
	return false;
}

int main(void){
	int n;
	cin >> n;
	rep(i,n) cin >> r[i];
	rep(i,n) x[i]=inf;
	
	rep(i,n){
		for(int j=-1;j<i;++j){
			double cx=r[i];
			if(j>=0){
				double d=1.0*(r[i]+r[j])*(r[i]+r[j]);
				d-=1.0*(r[i]-r[j])*(r[i]-r[j]);
				cx=x[j]+sqrt(d);
			}
			if(cx<r[i]) continue;
            if(i>0&&x[i-1]>=cx) continue;
            if(cross(i,cx,r[i])) continue;
            x[i]=min(x[i],cx);
		}
		// cerr << i << " " << x[i] << " " << r[i] << endl;
	}

	double ans=0.0;
	rep(i,n) ans=max(ans,x[i]+r[i]);
	cout.precision(20);
	assert(ans<inf);
	cout << fixed << ans << endl;
	return 0;
}