#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