e87d5512af 2011-06-03        kinaba: #include <iostream>
e87d5512af 2011-06-03        kinaba: #include <sstream>
e87d5512af 2011-06-03        kinaba: #include <iomanip>
e87d5512af 2011-06-03        kinaba: #include <vector>
e87d5512af 2011-06-03        kinaba: #include <string>
e87d5512af 2011-06-03        kinaba: #include <map>
e87d5512af 2011-06-03        kinaba: #include <set>
e87d5512af 2011-06-03        kinaba: #include <algorithm>
e87d5512af 2011-06-03        kinaba: #include <numeric>
e87d5512af 2011-06-03        kinaba: #include <iterator>
e87d5512af 2011-06-03        kinaba: #include <functional>
e87d5512af 2011-06-03        kinaba: #include <complex>
e87d5512af 2011-06-03        kinaba: #include <queue>
e87d5512af 2011-06-03        kinaba: #include <stack>
e87d5512af 2011-06-03        kinaba: #include <cmath>
e87d5512af 2011-06-03        kinaba: #include <cassert>
e87d5512af 2011-06-03        kinaba: #include <cstring>
e87d5512af 2011-06-03        kinaba: using namespace std;
e87d5512af 2011-06-03        kinaba: typedef long long LL;
e87d5512af 2011-06-03        kinaba: typedef complex<double> CMP;
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: class BarbarianInvasion2 { public:
e87d5512af 2011-06-03        kinaba: 	double minimumTime(vector <int> boundaryX, vector <int> boundaryY, vector <int> cityX, vector <int> cityY)
e87d5512af 2011-06-03        kinaba: 	{
e87d5512af 2011-06-03        kinaba: 		vector<CMP> b, c;
e87d5512af 2011-06-03        kinaba: 		for(int i=0; i<boundaryX.size(); ++i)
e87d5512af 2011-06-03        kinaba: 			b.push_back(CMP(boundaryX[i], boundaryY[i]));
e87d5512af 2011-06-03        kinaba: 		for(int i=0; i<cityX.size(); ++i)
e87d5512af 2011-06-03        kinaba: 			c.push_back(CMP(cityX[i], cityY[i]));
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 		double answer = 0;
e87d5512af 2011-06-03        kinaba: 		for(int i=0; i<b.size(); ++i)
e87d5512af 2011-06-03        kinaba: 			answer = max(answer, min_max(b[i], b[(i+1)%b.size()], c));
e87d5512af 2011-06-03        kinaba: 		return answer;
e87d5512af 2011-06-03        kinaba: 	}
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 	double min_max(CMP a, CMP b, vector<CMP> cs)
e87d5512af 2011-06-03        kinaba: 	{
e87d5512af 2011-06-03        kinaba: 		// return max[p on a-b] min[c in cs] |c-p|
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 		double factor = abs(b-a);
e87d5512af 2011-06-03        kinaba: 		{
e87d5512af 2011-06-03        kinaba: 			b -= a;
e87d5512af 2011-06-03        kinaba: 			for(int i=0; i<cs.size(); ++i)
e87d5512af 2011-06-03        kinaba: 				cs[i] -= a;
e87d5512af 2011-06-03        kinaba: 			for(int i=0; i<cs.size(); ++i)
e87d5512af 2011-06-03        kinaba: 				cs[i] /= b;
e87d5512af 2011-06-03        kinaba: 		}
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 		// return factor * max[p on 0-1] min[c in cs] |c-p|
e87d5512af 2011-06-03        kinaba: 		vector<double> ss;
e87d5512af 2011-06-03        kinaba: 		for(int i=0; i<cs.size(); ++i)
e87d5512af 2011-06-03        kinaba: 			for(int j=i+1; j<cs.size(); ++j)
e87d5512af 2011-06-03        kinaba: 				if( cs[i].real() != cs[j].real() )
e87d5512af 2011-06-03        kinaba: 					ss.push_back( sectpoint(cs[i], cs[j]) );
e87d5512af 2011-06-03        kinaba: 		sort(ss.begin(), ss.end());
e87d5512af 2011-06-03        kinaba: 		double fmin_max = 0.0;
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 		double z = 0.0;
e87d5512af 2011-06-03        kinaba: 		for(int i=0; i<ss.size(); ++i) {
e87d5512af 2011-06-03        kinaba: 			double t = min(1.0, ss[i]);
e87d5512af 2011-06-03        kinaba: 			if( t > z ) {
e87d5512af 2011-06-03        kinaba: 				// [z, t)
e87d5512af 2011-06-03        kinaba: 				{
e87d5512af 2011-06-03        kinaba: 					double pt = (z+t)/2;
e87d5512af 2011-06-03        kinaba: 					int minK = 0;
e87d5512af 2011-06-03        kinaba: 					for(int k=1; k<cs.size(); ++k)
e87d5512af 2011-06-03        kinaba: 						if( abs(cs[minK]-pt) > abs(cs[k]-pt) )
e87d5512af 2011-06-03        kinaba: 							minK = k;
e87d5512af 2011-06-03        kinaba: 					double fmin = furthest(z, t, cs[minK]);
e87d5512af 2011-06-03        kinaba: 					fmin_max = max(fmin_max, fmin);
e87d5512af 2011-06-03        kinaba: 				}
e87d5512af 2011-06-03        kinaba: 				z = t;
e87d5512af 2011-06-03        kinaba: 			}
e87d5512af 2011-06-03        kinaba: 			if( z>=1.0 )
e87d5512af 2011-06-03        kinaba: 				break;
e87d5512af 2011-06-03        kinaba: 		}
e87d5512af 2011-06-03        kinaba: 		if( z < 1.0 ) {
e87d5512af 2011-06-03        kinaba: 			double  t = 1.0;
e87d5512af 2011-06-03        kinaba: 			// [z, 1.0)
e87d5512af 2011-06-03        kinaba: 			{
e87d5512af 2011-06-03        kinaba: 				double pt = (z+t)/2;
e87d5512af 2011-06-03        kinaba: 				int minK = 0;
e87d5512af 2011-06-03        kinaba: 				for(int k=1; k<cs.size(); ++k)
e87d5512af 2011-06-03        kinaba: 					if( abs(cs[minK]-pt) > abs(cs[k]-pt) )
e87d5512af 2011-06-03        kinaba: 						minK = k;
e87d5512af 2011-06-03        kinaba: 				double fmin = furthest(z, t, cs[minK]);
e87d5512af 2011-06-03        kinaba: 				fmin_max = max(fmin_max, fmin);
e87d5512af 2011-06-03        kinaba: 			}
e87d5512af 2011-06-03        kinaba: 		}
e87d5512af 2011-06-03        kinaba: 		cerr << factor*fmin_max << endl;
e87d5512af 2011-06-03        kinaba: 		return factor * fmin_max;
e87d5512af 2011-06-03        kinaba: 	}
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 	double sectpoint(CMP a, CMP b)
e87d5512af 2011-06-03        kinaba: 	{
e87d5512af 2011-06-03        kinaba: 		CMP c = (a+b)/2.0;
e87d5512af 2011-06-03        kinaba: 		CMP dir = (a-b)*CMP(0,1);
e87d5512af 2011-06-03        kinaba: 		dir /= abs(dir);
e87d5512af 2011-06-03        kinaba: 		return (c + c.imag() / dir.imag() * dir).real();
e87d5512af 2011-06-03        kinaba: 	}
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: 	double furthest(double a, double b, CMP c)
e87d5512af 2011-06-03        kinaba: 	{
e87d5512af 2011-06-03        kinaba: 		if( c.real() > (a+b)/2 )
e87d5512af 2011-06-03        kinaba: 			return abs(c - a);
e87d5512af 2011-06-03        kinaba: 		else
e87d5512af 2011-06-03        kinaba: 			return abs(c - b);
e87d5512af 2011-06-03        kinaba: 	}
e87d5512af 2011-06-03        kinaba: };
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: // BEGIN CUT HERE
e87d5512af 2011-06-03        kinaba: #include <ctime>
e87d5512af 2011-06-03        kinaba: double start_time; string timer()
e87d5512af 2011-06-03        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
e87d5512af 2011-06-03        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
e87d5512af 2011-06-03        kinaba:  { os << "{ ";
e87d5512af 2011-06-03        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
e87d5512af 2011-06-03        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
e87d5512af 2011-06-03        kinaba: void verify_case(const double& Expected, const double& Received) {
e87d5512af 2011-06-03        kinaba:  bool ok = (abs(Expected - Received) < 1e-9);
e87d5512af 2011-06-03        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
e87d5512af 2011-06-03        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
e87d5512af 2011-06-03        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
e87d5512af 2011-06-03        kinaba: #define END	 verify_case(_, BarbarianInvasion2().minimumTime(boundaryX, boundaryY, cityX, cityY));}
e87d5512af 2011-06-03        kinaba: int main(){
e87d5512af 2011-06-03        kinaba: 
e87d5512af 2011-06-03        kinaba: CASE(0)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = {0,2,2,0};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = {0,0,2,2};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = {1};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = {1};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = 1.414213562373088;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: CASE(1)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = {0,3,3,0};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = {0,0,3,3};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = {1};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = {1};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = 2.8284271247461485;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: CASE(2)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = {0,3,3,0};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = {0,0,3,3};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = {1,2};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = {2,1};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = 2.236067977499772;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: CASE(3)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = {0,40,40,0};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = {0,0,40,40};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = {1,2,31,2,15};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = {1,2,3,3,24};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = 38.05748153551994;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: CASE(4)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = {0,124,-6,-120,-300};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = {0,125,140,137,-100};
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = {10,10,10,10};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = {50,51,52,21};
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = 332.77770358002783;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: /*
e87d5512af 2011-06-03        kinaba: CASE(5)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = ;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: CASE(6)
e87d5512af 2011-06-03        kinaba: 	int boundaryX_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_));
e87d5512af 2011-06-03        kinaba: 	int boundaryY_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_));
e87d5512af 2011-06-03        kinaba: 	int cityX_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_));
e87d5512af 2011-06-03        kinaba: 	int cityY_[] = ;
e87d5512af 2011-06-03        kinaba: 	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_));
e87d5512af 2011-06-03        kinaba: 	double _ = ;
e87d5512af 2011-06-03        kinaba: END
e87d5512af 2011-06-03        kinaba: */
e87d5512af 2011-06-03        kinaba: }
e87d5512af 2011-06-03        kinaba: // END CUT HERE