Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <string>
#include <set>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1005;

const double eps = 1e-10 , pi = acos(-1.0);
inline int dcmp(double x) {
    return (x > eps) - (x < -eps);
}

struct Point {
    double x , y;
    Point (double x = 0 , double y = 0) : x(x) , y(y) {} 
    void input() {
        scanf("%lf%lf",&x,&y);
    }
    bool operator < (const Point& R) const{
        if (dcmp(x - R.x) == 0)
            return dcmp(y - R.y) < 0;
        return dcmp(x - R.x) < 0;
    }
    bool operator == (const Point& R) const{
        return dcmp(x - R.x) == 0 && dcmp(y - R.y) == 0;
    }
    Point operator + (const Point& R) const{
        return Point(x + R.x , y + R.y);
    }
    Point operator - (const Point& R) const{
        return Point(x - R.x , y - R.y);
    }
    Point operator * (const double& R) const{
        return Point(x * R , y * R);
    }
    Point operator / (const double& R) const{
        return Point(x / R , y / R);
    }
    double operator ^ (const Point& R) const{
        return x * R.y - y * R.x;
    }
    double operator % (const Point& R) const{
        return x * R.x + y * R.y;
    }
    double len() {
        return sqrt(*this % *this);
    }
};

int n;
int R[N];
double pos[N];


bool check(int k , double r) {    
    for (int i = 0 ; i < k ; ++ i) {
        Point A(pos[i] , R[i]);
        Point B(r , R[k]);
        if (dcmp((A - B).len() - R[i] - R[k]) < 0)
            return 0;
    }
    return 1;
}

int main() {
    double res = 0;
    scanf("%d" , &n);
    for (int i = 0 ; i < n ; ++ i) {
        scanf("%d" , &R[i]);
        double l = max((i ? pos[i - 1] : 0.0) , (double)R[i]) , r = 2e7 , m;
        for (int T = 0 ; T < 100 ; ++ T) {
            m = 0.5 * (l + r);
            if (check(i , m))
                r = m;
            else
                l = m;
        }
        pos[i] = r;
        res = max(res , pos[i] + R[i]);
    }
    printf("%.10f\n" , res);
    return 0;
}