ADDED   SRM/507-U/1A.cpp
Index: SRM/507-U/1A.cpp
==================================================================
--- SRM/507-U/1A.cpp
+++ SRM/507-U/1A.cpp
@@ -0,0 +1,89 @@
+#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 CubeStickers { public:
+	string isPossible(vector <string> sticker) 
+	{
+		map<string,int> mp;
+		for(int i=0; i<sticker.size(); ++i)
+			mp[sticker[i]]++;
+		int cnt = 0;
+		for(map<string,int>::iterator it=mp.begin(); it!=mp.end(); ++it)
+			cnt += min(2, it->second);
+		return cnt>=6 ? "YES" : "NO";
+	}
+};
+
+// 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 string& Expected, const string& Received) {
+ bool ok = (Expected == Received);
+ 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(_, CubeStickers().isPossible(sticker));}
+int main(){
+
+CASE(0)
+	string sticker_[] = {"cyan","magenta","yellow","purple","black","white","purple"};
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = "YES"; 
+END
+CASE(1)
+	string sticker_[] = {"blue","blue","blue","blue","blue","blue","blue","blue","blue","blue"};
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = "NO"; 
+END
+CASE(2)
+	string sticker_[] = {"red","yellow","blue","red","yellow","blue","red","yellow","blue"};
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = "YES"; 
+END
+CASE(3)
+	string sticker_[] = {"purple","orange","orange","purple","black","orange","purple"};
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = "NO"; 
+END
+CASE(4)
+	string sticker_[] = {"white","gray","green","blue","yellow","red","target","admin"};
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = "YES"; 
+END
+/*
+CASE(5)
+	string sticker_[] = ;
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = ; 
+END
+CASE(6)
+	string sticker_[] = ;
+	  vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 
+	string _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/507-U/1B.cpp
Index: SRM/507-U/1B.cpp
==================================================================
--- SRM/507-U/1B.cpp
+++ SRM/507-U/1B.cpp
@@ -0,0 +1,103 @@
+#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 CubePacking { public:
+	int getMinimumVolume(int Ns, int Nb, int L) 
+	{
+		int m = L*L*L*Nb + Ns;
+		int M = L*L*L*Nb + Ns + L*L;
+		for(int c=m; c<=M; ++c) // <M should be fine, but just in case...
+		{
+			for(int p=1; p*p*p<=c; ++p) if( c%p == 0 )
+			for(int q=p; p*q*q<=c; ++q) if( c/p%q == 0 )
+			{
+				int r = c/p/q;
+				int nL = (p/L)*(q/L)*(r/L);
+				if( Nb <= nL )
+					return c;
+			}
+		}
+		assert(false);
+		return -1;
+	}
+};
+
+// 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 int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ 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(_, CubePacking().getMinimumVolume(Ns, Nb, L));}
+int main(){
+
+CASE(0)
+	int Ns = 2; 
+	int Nb = 2; 
+	int L = 2; 
+	int _ = 20; 
+END
+CASE(1)
+	int Ns = 19; 
+	int Nb = 1; 
+	int L = 2; 
+	int _ = 27; 
+END
+CASE(2)
+	int Ns = 51; 
+	int Nb = 7; 
+	int L = 5; 
+	int _ = 950; 
+END
+CASE(3)
+	int Ns = 12345; 
+	int Nb = 987; 
+	int L = 10; 
+	int _ = 999400; 
+END
+CASE(4)
+	int Ns = 1000000000; 
+	int Nb = 1000000; 
+	int L = 10; 
+	int _ = -1; 
+END
+CASE(5)
+	int Ns = 1; 
+	int Nb = 1; 
+	int L = 1; 
+	int _ = 2; 
+END
+CASE(5)
+	int Ns = 1; 
+	int Nb = 1; 
+	int L = 2; 
+	int _ = 12; 
+END
+
+}
+// END CUT HERE

ADDED   SRM/507-U/1C-U.cpp
Index: SRM/507-U/1C-U.cpp
==================================================================
--- SRM/507-U/1C-U.cpp
+++ SRM/507-U/1C-U.cpp
@@ -0,0 +1,172 @@
+#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;
+
+static const int MODVAL = 1000000007; // must be prime for op/
+struct mint
+{
+	int val;
+	mint():val(0){}
+	mint(int x):val(x%MODVAL) {}
+	mint(LL  x):val(x%MODVAL) {}
+};
+mint operator+(mint x, mint y) { return x.val+y.val; }
+mint operator*(mint x, mint y) { return LL(x.val)*y.val; }
+mint POW(mint x, int e) {
+	mint v = 1;
+	for(;e;x=x*x,e>>=1)
+		if(e&1)
+			v=v*x;
+	return v;
+}
+mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); }
+vector<mint> FAC_(1,1);
+void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*int(FAC_.size()) ); }
+mint FAC(int x)      { return FAC_[x]; }
+
+class CubeBuilding { public:
+	int getCount(int R, int G, int B, int N) 
+	{
+		FAC_INIT(25);
+		memo2.assign(26*26*26*26, -1);
+		memo2all.assign(26*26*26*26, -1);
+		memo3.assign(26*26*26*26, -1);
+		return (dim3(R,G,B,N,N)+dim3(G,B,R,N,N)+dim3(B,G,R,N,N)).val;
+	}
+
+	vector<int> memo3;
+	mint dim3(int R, int G, int B, int n, int N)
+	{
+		if( n == 0 )
+			return (R+G+B==0 ? 1 : 0);
+
+		if(G>B) swap(G,B);
+		int key = ((R*26+G)*26+B)*26+n;
+		if( memo3[key] >= 0 )
+			return memo3[key];
+
+		mint total = 0;
+		for(int r=0; r<=R; ++r)
+			for(int g=0; g<=G; ++g)
+				for(int b=0; b<=B; ++b)
+					total = total + dim2all(r,g,b,N)*dim3(R-r,G-g,B-b,n-1,N);
+		memo3[key] = total.val;
+		return total;
+	}
+
+	vector<int> memo2;
+	mint dim2(int R, int G, int B, int n)
+	{
+		if( n == 0 ) return (R+G+B==0 ? 1 : 0);
+		if( R == 0 ) return (G+B==0 ? 1 : 0);
+
+		if(G>B) swap(G,B);
+		int key = ((R*26+G)*26+B)*26+n;
+		if( memo2[key] >= 0 )
+			return memo2[key];
+
+		mint total = 0;
+		for(int r=1; r<=R; ++r)
+			for(int g=0; g<=G; ++g) {
+				int b = n-r-g;
+				if( 0<=b && b<=B )
+					total = total + dim2all(R-r,G-g,B-b,n) * (FAC(n-1)/FAC(r-1)/FAC(g)/FAC(b));
+			}
+		memo2[key] = total.val;
+		return total;
+	}
+
+	vector<int> memo2all;
+	mint dim2all(int R, int G, int B, int n)
+	{
+		int key = ((R*26+G)*26+B)*26+n;
+		if( memo2all[key] >= 0 )
+			return memo2all[key];
+
+		mint total = 0;
+		for(int m=0; m<=n; ++m)
+			total = total + dim2(R,G,B,m)*(FAC(n)/FAC(m)/FAC(n-m));
+		memo2all[key] = total.val;
+		return total;
+	}
+};
+
+// 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 int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ 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(_, CubeBuilding().getCount(R, G, B, N));}
+int main(){
+
+CASE(0)
+	int R = 1; 
+	int G = 0; 
+	int B = 1; 
+	int N = 2; 
+	int _ = 4; 
+END
+CASE(1)
+	int R = 1; 
+	int G = 1; 
+	int B = 2; 
+	int N = 1; 
+	int _ = 0; 
+END
+CASE(2)
+	int R = 2; 
+	int G = 2; 
+	int B = 1; 
+	int N = 3; 
+	int _ = 162; 
+END
+CASE(3)
+	int R = 0; 
+	int G = 0; 
+	int B = 10; 
+	int N = 12; 
+	int _ = 372185933; 
+END
+CASE(4)
+	int R = 25; 
+	int G = 25; 
+	int B = 25; 
+	int N = 25; 
+	int _ = -1; 
+END
+/*
+CASE(5)
+	int R = ; 
+	int G = ; 
+	int B = ; 
+	int N = ; 
+	int _ = ; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/508-U/1A.cpp
Index: SRM/508-U/1A.cpp
==================================================================
--- SRM/508-U/1A.cpp
+++ SRM/508-U/1A.cpp
@@ -0,0 +1,113 @@
+#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 DivideAndShift { public:
+	int getLeast(int N, int M) 
+	{
+		--M;
+		int best = 0x7fffffff;
+		for(int d=1; d*d<=N; ++d)
+			if( N%d == 0 )
+			{
+				best = min(best, divStep(N/d)+shiftDist(M%d, d));
+				best = min(best, divStep(d)+shiftDist(M%(N/d), N/d));
+			}
+		return best;
+	}
+
+	int shiftDist(int k, int P)
+	{
+		return min(k, P-k);
+	}
+
+	int divStep(int n)
+	{
+		int c = 0;
+		for(int p=2; p*p<=n; ++p)
+			while(n%p==0) {n/=p; ++c;}
+		return c + (n>1);
+	}
+};
+
+// 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 int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ 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(_, DivideAndShift().getLeast(N, M));}
+int main(){
+
+CASE(0)
+	int N = 56; 
+	int M = 14; 
+	int _ = 3; 
+END
+CASE(1)
+	int N = 49; 
+	int M = 5; 
+	int _ = 2; 
+END
+CASE(2)
+	int N = 256; 
+	int M = 7; 
+	int _ = 6; 
+END
+CASE(3)
+	int N = 6; 
+	int M = 1; 
+	int _ = 0; 
+END
+CASE(4)
+	int N = 77777; 
+	int M = 11111; 
+	int _ = 2; 
+END
+CASE(5)
+	int N = 1000000; 
+	int M = 1000000; 
+	int _ = -1; 
+END
+CASE(6)
+	int N = 1000000; 
+	int M =  999997; 
+	int _ = -1; 
+END
+CASE(7)
+	int N = 1; 
+	int M = 1; 
+	int _ = 0; 
+END
+CASE(8)
+	int N = 997*997; 
+	int M = 444; 
+	int _ = -1; 
+END
+
+}
+// END CUT HERE

ADDED   SRM/508-U/1B.cpp
Index: SRM/508-U/1B.cpp
==================================================================
--- SRM/508-U/1B.cpp
+++ SRM/508-U/1B.cpp
@@ -0,0 +1,105 @@
+#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 YetAnotherORProblem { public:
+	map<vector<LL>, int> memo;
+	int countSequences(const vector<LL>& R) 
+	{
+		if( count(R.begin(),R.end(),0) == R.size() )
+			return 1;
+		if( memo.count(R) )
+			return memo[R];
+
+		vector<LL> RR;
+		for(int i=0; i<R.size(); ++i)
+			RR.push_back(R[i]/2);
+
+		int total = countSequences(RR);
+		for(int i=0; i<R.size(); ++i)
+			if( R[i] )
+			{
+				if( (R[i]&1) == 0 ) RR[i]--;
+				total = (total + countSequences(RR)) % 1000000009;
+				if( (R[i]&1) == 0 ) RR[i]++;
+			}
+		return memo[R] = total;
+	}
+};
+
+// 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 int& Expected, const int& Received) {
+ bool ok = (Expected == Received);
+ 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(_, YetAnotherORProblem().countSequences(R));}
+int main(){
+
+CASE(0)
+	long R_[] = {3,5};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 15; 
+END
+CASE(1)
+	long R_[] = {3,3,3};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 16; 
+END
+CASE(2)
+	long R_[] = {1,128};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 194; 
+END
+CASE(3)
+	long R_[] = {26,74,25,30};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 8409; 
+END
+CASE(4)
+	long R_[] = {1000000000,1000000000};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 420352509; 
+END
+CASE(5)
+long long R_[] = {1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = -1; 
+END
+CASE(6)
+	long long R_[] = {1, 1};
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 3; 
+END
+CASE(6)
+	long long R_[] = {0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, };
+	  vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); 
+	int _ = 3; 
+END
+
+}
+// END CUT HERE

ADDED   SRM/508-U/1C-U.cpp
Index: SRM/508-U/1C-U.cpp
==================================================================
--- SRM/508-U/1C-U.cpp
+++ SRM/508-U/1C-U.cpp
@@ -0,0 +1,208 @@
+#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