Artifact Content
Not logged in

Artifact 7d4184f5c5d549e916ca42fa25a9e7378499f61b


#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