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){//info[k].x,info[k].r,m  m = (left+right)/2,tmp_r
    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;//double left_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;
}