Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

double r[500];
double pos[500];

bool check(double r1, double p1, double r2, double p2){
	double dx = p1 - p2, dy = r1 - r2;
	double d = sqrt(dx * dx + dy * dy);
	return d <= r1 + r2;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N;
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> r[i];
	}

	for(int i = 1; i < N; i++){
		double ng = pos[i - 1], ok = 1e9;
		for(int loop = 0; loop < 200; loop++){
			double mid = (ok + ng) / 2;
			bool flag = true;
			for(int j = 0; j < i; j++){
				if(check(r[j], pos[j], r[i], mid)){
					flag = false;
					break;
				}
			}
			if(flag) ok = mid;
			else ng = mid;
		}
		pos[i] = ok;
	}

	double minx = 1e9, maxx = -1e9;
	for(int i = 0; i < N; i++){
		minx = min(minx, pos[i] - r[i]);
		maxx = max(maxx, pos[i] + r[i]);
	}
	cout << fixed << setprecision(15) << maxx - minx << endl;
}