Problem: Example

Input

2
10 10


Output

40.00000000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q>
ostream& operator << (ostream& os, pair<P, Q> p)
{
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

typedef complex<double> P;

struct C {
  P o;
  double r;
  C() {}
  C(P o, double r) : o(o), r(r) {}
};

const double eps = 1e-8;
const double pi = acos(-1);

bool equals(double a, double b) { return abs(a - b) < eps; }

int isIntersect(C a, C b) {
  double x = a.o.real() - b.o.real();
  double y = a.o.imag() - b.o.imag();
  double s = a.r + b.r;
  double d = x*x + y*y;
  s *= s;
  if(equals(d, s)) return 1;
  if(d > s) return 0;
  double r = abs(a.r - b.r);
  r *= r;
  if(equals(d, r)) return -1;
  if(d > r) return 2;
  return -2;
}

int main(int argc, char *argv[])
{
  int n;
  while (cin >> n) {
    int r[n];
    for (int i = 0; i < n; ++i) {
      cin >> r[i];
    }
    double x[n];
    x[0] = r[0];
    for (int i = 1; i < n; ++i) {
      x[i] = -1e128;
      for (int j = 0; j < i; ++j) {
        double small = max<double>(x[j], r[i]);
        double large = 1e128;
        for (int loop = 1000; loop--; ) {
          double mid = (small + large) / 2.0;
          C a(P(x[j], r[j]), r[j]);
          C b(P(mid,  r[i]), r[i]);
          if (isIntersect(a, b)) small = mid;
          else large = mid;
        }
        x[i] = max(x[i], large);
      }
    }
    double mx = 0;
    for (int i = 0; i < n; ++i) {
      mx = max(mx, x[i] + r[i]);
    }
    printf("%.10lf\n", mx);
  }
  return 0;
}