Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD NUM000007
#define EPS 0.0000001
#define NUM 30000
using namespace std;

struct Info{
	double x,r;
};

double calc_dist(double left_x,double left_y,double right_x,double right_y){
	return sqrt((left_x-right_x)*(left_x-right_x)+(left_y-right_y)*(left_y-right_y));
}

int main(){

	int N;
	double tmp_r,tmp,maximum;
	double left,right,m,dist,tmp_loc;
	Info info[501];

	scanf("%d",&N);
	scanf("%lf",&tmp_r);
	info[0].x = tmp_r;
	info[0].r = tmp_r;


	for(int i = 1; i <= N-1; i++){

		scanf("%lf",&tmp_r);

		info[i].r = tmp_r;
		maximum = 0;
		for(int k = 0; k < i; k++){

			left = info[k].x;
			right = info[k].x+info[k].r+tmp_r;
			m = (left+right)/2;

			dist = info[k].r+tmp_r;

			while(left<=right){
				tmp = calc_dist(info[k].x,info[k].r,m,tmp_r);

				if(abs(dist-tmp) < EPS){ //OK
					tmp_loc = m;
					if(tmp_loc < tmp_r)tmp_loc = tmp_r;
					break;
				}else{
					if(tmp > dist){
						right = m-EPS;
					}else{
						left = m+EPS;
					}
				}
				m = (left+right)/2;
			}
			maximum = max(maximum,tmp_loc);
		}
		info[i].x = maximum;
	}

	maximum = 0.0;
	for(int i = 0; i < N; i++)maximum = max(maximum,info[i].x+info[i].r);

	printf("%.8lf\n",maximum);

	return 0;
}