#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
struct Circle {
CMP o;
double r;
};
bool line_circle(CMP la, CMP lb, CMP c, double r, CMP* p1, CMP* p2)
{
CMP v = (lb-la) / abs(lb-la);
CMP o = (c-la) / v;
if( abs(o.imag()) > r )
return false;
double dx = sqrt(r*r - o.imag()*o.imag());
*p1 = la + (o.real()-dx)*v;
*p2 = la + (o.real()+dx)*v;
return true;
}
class CircusTents { public:
double findMaximumDistance(vector <int> x, vector <int> y, vector <int> r)
{
double f = r[0];
vector<Circle> cs;
for(int i=1; i<x.size(); ++i) {
Circle you = {CMP(x[1]-x[0], y[1]-y[0])/f, double(r[1])/f};
cs.push_back(you);
}
return solve(cs) * f;
}
double solve(const vector<Circle>& cs)
{
vector<double> args;
for(int i=0; i<cs.size(); ++i)
for(int k=i+1; k<cs.size(); ++k) {
CMP p = cs[i].o;
CMP q = cs[k].o;
double len = abs(q-p);
double mid = (len - cs[i].r - cs[k].r)/2+cs[i].r;
CMP r = (q-p)/len*mid;
CMP d = (q-p)/len*CMP(0,1);
/// r + td is the splitting line.
CMP x1, x2;
if( line_circle(r, r+d, CMP(0,0), 1.0, &x1, &x2) ) {
args.push_back(arg(x1));
args.push_back(arg(x2));
}
}
if(args.empty()) {
args.push_back(0.0);
args.push_back(1.0);
}
sort(args.begin(), args.end());
double best = 0.0;
for(int i=0; i<args.size(); ++i) {
double aL = args[i];
double aR = (i+1==args.size() ? args[0]+M_PI/2 : args[i+1]);
double aC = (aL+aR) / 2;
CMP p = polar(1.0, aC);
int close = -1; double close_d = 999999999;
for(int k=0; k<cs.size(); ++k) {
double d = abs(p - cs[k].o) - cs[k].r;
if(d<close_d) {close=k, close_d=d;}
}
CMP pL = polar(1.0, aL);
CMP pR = polar(1.0, aR);
CMP v = cs[close].o;
pL /= v/abs(v);
pR /= v/abs(v);
double aaL = arg(pL);
double aaR = arg(pR);
double theA;
if(aaL > aaR) {
theA = M_PI;
} else {
theA = (abs(aaL)>abs(aaR) ? aaL : aaR);
}
// distance from polar(1.0, theA) to Circ((abs(v),0), cs[close].r)
// ... avoiding the two circle!
double ddd = 0;
cerr<<polar(1.0, theA)<<endl;
best = min(best, ddd);
}
return best;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const double& Expected, const double& Received) {
bool ok = (abs(Expected - Received) < 1e-9);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, CircusTents().findMaximumDistance(x, y, r));}
int main(){
CASE(0)
int x_[] = {0,3};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {0,0};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = {1,1};
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = 3.7390603609952078;
END
CASE(1)
int x_[] = {0,3,-3,3,-3};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {0,3,3,-3,-3};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = {1,1,1,1,1};
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = 2.6055512754639887;
END
CASE(2)
int x_[] = {3,7,7,7,3};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {4,6,1,-3,0};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = {2,2,2,1,1};
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = 4.3264459099620725;
END
CASE(3)
int x_[] = {10,-1};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {0,0};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = {8,2};
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = 24.63092458664212;
END
CASE(4)
int x_[] = {0,4,-4};
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = {0,4,-4};
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = {1,1,1};
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = 4.745474963675133;
END
/*
CASE(5)
int x_[] = ;
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = ;
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = ;
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = ;
END
CASE(6)
int x_[] = ;
vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
int y_[] = ;
vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
int r_[] = ;
vector <int> r(r_, r_+sizeof(r_)/sizeof(*r_));
double _ = ;
END
*/
}
// END CUT HERE