Artifact Content
Not logged in

Artifact 1ce44cdd43d689dbecea3c8cbb76b76ac57e552c


#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>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class BarbarianInvasion2 { public:
	double minimumTime(vector <int> boundaryX, vector <int> boundaryY, vector <int> cityX, vector <int> cityY) 
	{
		vector<CMP> b, c;
		for(int i=0; i<boundaryX.size(); ++i)
			b.push_back(CMP(boundaryX[i], boundaryY[i]));
		for(int i=0; i<cityX.size(); ++i)
			c.push_back(CMP(cityX[i], cityY[i]));

		double answer = 0;
		for(int i=0; i<b.size(); ++i)
			answer = max(answer, min_max(b[i], b[(i+1)%b.size()], c));
		return answer;
	}

	double min_max(CMP a, CMP b, vector<CMP> cs)
	{
		// return max[p on a-b] min[c in cs] |c-p|

		double factor = abs(b-a);
		{
			b -= a;
			for(int i=0; i<cs.size(); ++i)
				cs[i] -= a;
			for(int i=0; i<cs.size(); ++i)
				cs[i] /= b;
		}

		// return factor * max[p on 0-1] min[c in cs] |c-p|
		vector<double> ss;
		for(int i=0; i<cs.size(); ++i)
			for(int j=i+1; j<cs.size(); ++j)
				if( cs[i].real() != cs[j].real() )
					ss.push_back( sectpoint(cs[i], cs[j]) );
		sort(ss.begin(), ss.end());
		double fmin_max = 0.0;

		double z = 0.0;
		for(int i=0; i<ss.size(); ++i) {
			double t = min(1.0, ss[i]);
			if( t > z ) {
				// [z, t)
				{
					double pt = (z+t)/2;
					int minK = 0;
					for(int k=1; k<cs.size(); ++k)
						if( abs(cs[minK]-pt) > abs(cs[k]-pt) )
							minK = k;
					double fmin = furthest(z, t, cs[minK]);
					fmin_max = max(fmin_max, fmin);
				}
				z = t;
			}
			if( z>=1.0 )
				break;
		}
		if( z < 1.0 ) {
			double  t = 1.0;
			// [z, 1.0)
			{
				double pt = (z+t)/2;
				int minK = 0;
				for(int k=1; k<cs.size(); ++k)
					if( abs(cs[minK]-pt) > abs(cs[k]-pt) )
						minK = k;
				double fmin = furthest(z, t, cs[minK]);
				fmin_max = max(fmin_max, fmin);
			}
		}
		cerr << factor*fmin_max << endl;
		return factor * fmin_max;
	}

	double sectpoint(CMP a, CMP b)
	{
		CMP c = (a+b)/2.0;
		CMP dir = (a-b)*CMP(0,1);
		dir /= abs(dir);
		return (c + c.imag() / dir.imag() * dir).real();
	}

	double furthest(double a, double b, CMP c)
	{
		if( c.real() > (a+b)/2 )
			return abs(c - a);
		else
			return abs(c - b);
	}
};

// 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(_, BarbarianInvasion2().minimumTime(boundaryX, boundaryY, cityX, cityY));}
int main(){

CASE(0)
	int boundaryX_[] = {0,2,2,0};
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = {0,0,2,2};
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = {1};
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = {1};
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = 1.414213562373088; 
END
CASE(1)
	int boundaryX_[] = {0,3,3,0};
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = {0,0,3,3};
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = {1};
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = {1};
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = 2.8284271247461485; 
END
CASE(2)
	int boundaryX_[] = {0,3,3,0};
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = {0,0,3,3};
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = {1,2};
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = {2,1};
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = 2.236067977499772; 
END
CASE(3)
	int boundaryX_[] = {0,40,40,0};
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = {0,0,40,40};
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = {1,2,31,2,15};
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = {1,2,3,3,24};
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = 38.05748153551994; 
END
CASE(4)
	int boundaryX_[] = {0,124,-6,-120,-300};
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = {0,125,140,137,-100};
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = {10,10,10,10};
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = {50,51,52,21};
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = 332.77770358002783; 
END
/*
CASE(5)
	int boundaryX_[] = ;
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = ;
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = ;
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = ;
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = ; 
END
CASE(6)
	int boundaryX_[] = ;
	  vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 
	int boundaryY_[] = ;
	  vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 
	int cityX_[] = ;
	  vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); 
	int cityY_[] = ;
	  vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); 
	double _ = ; 
END
*/
}
// END CUT HERE