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