ADDED   SRM/543/1A.cpp
Index: SRM/543/1A.cpp
==================================================================
--- SRM/543/1A.cpp
+++ SRM/543/1A.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>
+#ifdef __GNUC__
+#include <ext/hash_map>
+#define unordered_map __gnu_cxx::hash_map
+#else
+#include <unordered_map>
+#endif
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class EllysXors { public:
+	long long getXor(long long L, long long R)
+	{
+		if( R-L < 5 ) {
+			LL a = 0;
+			for(LL v=L; v<=R; ++v)
+				a ^= v;
+			return a;
+		}
+
+		LL a = 0;
+		if( L%2 == 1 ) {
+			a ^= L;
+			++L;
+		}
+		if( R%2 == 0 ) {
+			a ^= R;
+			--R;
+		}
+		return a ^ ((R+1-L)/2%2);
+	}
+};
+
+// 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 long long& Expected, const long long& 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(_, EllysXors().getXor(L, R));}
+int main(){
+
+CASE(0)
+	long long L = 3LL; 
+	long long R = 10LL; 
+	long long _ = 8LL; 
+END
+CASE(1)
+	long long L = 5LL; 
+	long long R = 5LL; 
+	long long _ = 5LL; 
+END
+CASE(2)
+	long long L = 13LL; 
+	long long R = 42LL; 
+	long long _ = 39LL; 
+END
+CASE(3)
+	long long L = 666LL; 
+	long long R = 1337LL; 
+	long long _ = 0LL; 
+END
+CASE(4)
+	long long L = 1234567LL; 
+	long long R = 89101112LL; 
+	long long _ = 89998783LL; 
+END
+/*
+CASE(5)
+	long long L = LL; 
+	long long R = LL; 
+	long long _ = LL; 
+END
+CASE(6)
+	long long L = LL; 
+	long long R = LL; 
+	long long _ = LL; 
+END
+*/
+}
+// END CUT HERE

ADDED   SRM/543/1B.cpp
Index: SRM/543/1B.cpp
==================================================================
--- SRM/543/1B.cpp
+++ SRM/543/1B.cpp
@@ -0,0 +1,144 @@
+#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 long double LD;
+typedef complex<LD> CMP;
+
+template<typename T>
+struct DP2x
+{
+	const int N1, N2;
+	vector<T> data;
+	DP2x(int, int N2, const T& t = T())
+		: N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
+	T& operator()(int i1, int i2)
+		{ i1&=1; return data[ (i1*N2)+i2 ]; }
+	void swap(DP2x& rhs)
+		{ data.swap(rhs.data); }
+};
+
+class EllysRivers { public:
+	double getMin(int length, int walk, vector <int> width, vector <int> speed)
+	{
+		DP2x<LD> dp(width.size()+1, length+1);
+		for(int x=0; x<=length; ++x)
+			dp(0,x) = x / LD(walk);
+
+		for(int y=1; y<=width.size(); ++y) {
+			LD w = width[y-1];
+			LD s = speed[y-1];
+
+			for(int x=length,px=length; x>=0; --x) {
+			retry:
+				LD t = dp(y-1, px) + sqrt(LD(px-x)*(px-x) + w*w) / s;
+				if( px > 0 ) {
+					LD tt = dp(y-1, px-1) + sqrt(LD(px-1-x)*(px-1-x) + w*w) / s;
+					if( tt < t ) {
+						--px;
+						goto retry;
+					}
+				}
+				dp(y, x) = t;
+			}
+		}
+
+		return dp(width.size(), length);
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+LD 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 LD& Expected, const LD& 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(_, EllysRivers().getMin(length, walk, width, speed));}
+int main(){
+
+CASE(0)
+	int length = 10; 
+	int walk = 3; 
+	int width_[] = {5, 2, 3};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {5, 2, 7};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 3.231651964071508; 
+END
+CASE(1)
+	int length = 10000; 
+	int walk = 211; 
+	int width_[] = {911};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {207};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 48.24623664712219; 
+END
+CASE(2)
+	int length = 1337; 
+	int walk = 2; 
+	int width_[] = {100, 200, 300, 400};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {11, 12, 13, 14};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 128.57830549575695; 
+END
+CASE(3)
+	int length = 77; 
+	int walk = 119; 
+	int width_[] = {11, 12, 13, 14};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {100, 200, 300, 400};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 0.3842077071089629; 
+END
+CASE(4)
+	int length = 7134; 
+	int walk = 1525; 
+	int width_[] = {11567, 19763, 11026, 10444, 24588, 22263, 17709, 11181, 15292, 28895, 15039, 18744, 19985, 13795, 26697, 18812, 25655, 13620, 28926, 12393};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {1620, 1477, 2837, 2590, 1692, 2270, 1655, 1078, 2683, 1475, 1383, 1153, 1862, 1770, 1671, 2318, 2197, 1768, 1979, 1057};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 214.6509731258811; 
+END
+CASE(5)
+	int length = 100000; 
+	int walk = 1; 
+	int width_[] = {1000000, 1000000, 1000000};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {1, 1000000, 1};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 2000001.004987562; 
+END
+CASE(6)
+	int length = 100000; 
+	int walk = 1; 
+	int width_[] = {1000000, 1000000, 1000000};
+	  vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_)); 
+	int speed_[] = {1000000, 1000000, 1};
+	  vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_)); 
+	LD _ = 1000002.0024984397; 
+END
+}
+// END CUT HERE

ADDED   SRM/543/1C.cpp
Index: SRM/543/1C.cpp
==================================================================
--- SRM/543/1C.cpp
+++ SRM/543/1C.cpp
@@ -0,0 +1,277 @@
+#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 long double LD;
+typedef complex<LD> CMP;
+
+struct Ship {
+	CMP s, e;
+	LD speed;
+	LD r;
+	LD energy;
+};
+
+template<typename T>
+class IdGen
+{
+	map<T, int> v2id_;
+	vector<T>   id2v_;
+public:
+	int v2id(const T& v) {
+		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
+		return v2id_[v];
+	}
+	const T& id2v(int i) const { return id2v_[i]; }
+	int size() const { return id2v_.size(); }
+};
+
+template<typename Vert, typename Flow, int NV=512>
+class MaxFlow
+{
+	IdGen<Vert> idgen;
+	vector<int> G[NV];
+	Flow F[NV][NV];
+
+public:
+	void addEdge( Vert s_, Vert t_, Flow f )
+	{
+		const int s = idgen.v2id(s_), t = idgen.v2id(t_);
+		G[s].push_back(t);
+		G[t].push_back(s);
+		F[s][t] = f;
+		F[t][s] = 0;
+	}
+
+	Flow calc( Vert s_, Vert t_ )
+	{
+		const int S = idgen.v2id(s_), D = idgen.v2id(t_);
+		for( Flow total=0 ;; ) {
+			// Do BFS and compute the level for each node.
+			int LV[NV] = {0};
+			vector<int> Q(1, S);
+			for(int lv=1; !Q.empty(); ++lv) {
+				vector<int> Q2;
+				for(size_t i=0; i!=Q.size(); ++i) {
+					const vector<int>& ne = G[Q[i]];
+					for(size_t j=0; j!=ne.size(); ++j)
+						if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
+							LV[ne[j]]=lv, Q2.push_back(ne[j]);
+				}
+				Q.swap(Q2);
+			}
+
+			// Destination is now unreachable. Done.
+			if( !LV[D] )
+				return total;
+
+			// Iterating DFS.
+			bool blocked[NV] = {};
+			total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
+		}
+	}
+
+private:
+	Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
+	{
+		Flow flow_out = 0;
+		for(size_t i=0; i!=G[v].size(); ++i) {
+			int u = G[v][i];
+			if( LV[v]+1==LV[u] && F[v][u] ) {
+				Flow f = min(flow_in-flow_out, F[v][u]);
+				if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
+					F[v][u]  -= f;
+					F[u][v]  += f;
+					flow_out += f;
+					if( flow_in == flow_out ) return flow_out;
+				}
+			}
+		}
+		blocked[v] = (flow_out==0);
+		return flow_out;
+	}
+};
+
+bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
+{
+	CMP v = (lb-la) / abs(lb-la);
+	CMP o = (c-la) / v;
+	if( abs(o.imag()) > r )
+		return false;
+	LD dx = sqrt(r*r - o.imag()*o.imag());
+	*p1 = la + (o.real()-dx)*v;
+	*p2 = la + (o.real()+dx)*v;
+	return true;
+}
+
+class EllysDeathStars { public:
+	double getMax(vector <string> stars_, vector <string> ships_)
+	{
+		vector<CMP> stars;
+		for(int i=0; i<stars_.size(); ++i)
+		{
+			stringstream sin(stars_[i]);
+			int x, y;
+			sin >> x >> y;
+			stars.push_back(CMP(x,y));
+		}
+		vector<Ship> ships;
+		for(int i=0; i<ships_.size(); ++i)
+		{
+			stringstream sin(ships_[i]);
+			int sx, sy, ex, ey, s, r, e;
+			sin >> sx >> sy >> ex >> ey >> s >> r >> e;
+			Ship ship;
+			ship.s = CMP(sx,sy);
+			ship.e = CMP(ex,ey);
+			if(ship.s == ship.e)
+				continue;
+			ship.speed = s;
+			ship.r = r;
+			ship.energy = e;
+			ships.push_back(ship);
+		}
+		return solve(stars, ships);
+	}
+
+	LD solve(const vector<CMP>& stars, const vector<Ship>& ships)
+	{
+		typedef pair<int, int> Vert;
+		MaxFlow<Vert, LD, 2048>* mf = new MaxFlow<Vert, LD, 2048>();
+		for(int b=0; b<ships.size(); ++b)
+			mf->addEdge(Vert(0,0), Vert(1,b), ships[b].energy);
+
+		int id = 0;
+		for(int a=0; a<stars.size(); ++a) {
+			vector<LD> events;
+			events.push_back(0);
+			for(int b=0; b<ships.size(); ++b)
+				events.push_back(abs(ships[b].e-ships[b].s) / ships[b].speed);
+			LD lasttime = *max_element(events.begin(), events.end());
+
+			for(int b=0; b<ships.size(); ++b) {
+				CMP p = ships[b].s;
+				CMP q = ships[b].e;
+				CMP o = stars[a];
+				LD r = ships[b].r;
+				LD speed = ships[b].speed;
+
+				o = (o - p) / ((q-p) / abs(q-p));
+				LD y = abs(o.imag());
+				if( y < r ) {
+					LD dx = sqrt(r*r - y*y);
+					LD x1 = o.real() - dx;
+					LD x2 = o.real() + dx;
+					if(0<x1/speed && x1/speed<lasttime)
+						events.push_back( x1 / speed );
+					if(0<x2/speed && x2/speed<lasttime)
+						events.push_back( x2 / speed );
+				}
+			}
+			sort(events.begin(), events.end());
+
+			for(int i=0; i+1<events.size(); ++i, ++id) {
+				LD sec = events[i+1] - events[i];
+				LD mid = (events[i+1] + events[i]) / 2;
+				for(int b=0; b<ships.size(); ++b) {
+					LD rng = abs(ships[b].e - ships[b].s) / ships[b].speed;
+					CMP pos = ships[b].s + (ships[b].e-ships[b].s)/abs(ships[b].e-ships[b].s)*ships[b].speed*mid;
+					if( 0<mid && mid<rng && abs(pos-stars[a])<ships[b].r)
+						mf->addEdge(Vert(1,b), Vert(2,id), sec);
+				}
+				mf->addEdge(Vert(2,id), Vert(3,0), sec);
+			}
+		}
+
+		LD flow = mf->calc(Vert(0,0), Vert(3,0));
+		delete mf;
+		return flow;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+LD 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 LD& Expected, const LD& 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(_, EllysDeathStars().getMax(stars, ships));}
+int main(){
+
+CASE(0)
+	string stars_[] = {"2 2"};
+	  vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); 
+	string ships_[] = {"1 1 5 3 2 1 2"};
+	  vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); 
+	LD _ = 0.894427190999916; 
+END
+CASE(1)
+	string stars_[] = {"12 10", "7 5"};
+	  vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); 
+	string ships_[] = {"10 10 12 10 1 1 3", "6 1 8 10 1 2 3", "3 6 8 2 5 3 1", "42 42 42 42 6 6 6"};
+	  vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); 
+	LD _ = 4.983770744659944; 
+END
+CASE(2)
+	string stars_[] = {"5 77", "60 50", "10 46", "22 97", "87 69"};
+	  vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); 
+	string ships_[] = {"42 17 66 11 5 7 13", "10 10 20 20 3 3 3", "13 15 18 9 4 1 2",
+ "99 71 63 81 19 4 60", "27 34 56 43 11 3 12"};
+	  vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); 
+	LD _ = 0.0; 
+END
+CASE(3)
+	string stars_[] = {"141 393", "834 847", "568 43", "18 228", "515 794",
+ "167 283", "849 333", "719 738", "434 261", "613 800",
+ "127 340", "466 938", "598 601"};
+	  vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); 
+	string ships_[] = {"410 951 472 100 337 226 210", "713 352 677 908 731 687 300",
+ "191 41 337 92 446 716 213", "598 889 446 907 148 650 203",
+ "168 556 470 924 344 369 198", "300 182 350 936 737 533 45",
+ "410 871 488 703 746 631 80", "270 777 636 539 172 103 56",
+ "466 906 522 98 693 77 309", "768 698 846 110 14 643 14",
+ "755 724 664 465 263 759 120"};
+	  vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); 
+	LD _ = 31.965770956316362; 
+END
+CASE(4)
+	string stars_[] = 
+{"20 1", "70 1", "120 1", "170 1", "220 1", "270 1", "320 1", "370 1", "420 1", "470 1", "520 1", "570 1", "620 1", "670 1", "720 1", "770 1", "820 1", "870 1", "920 1", "970 1"}
+;
+	  vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); 
+	string ships_[] =
+		{"1 21 1000 21 1 21 257", "1 20 1000 20 1 21 102", "1 19 1000 19 1 21 75", "1 18 1000 18 1 21 61", "1 17 1000 17 1 21 51", "1 16 1000 16 1 21 44", "1 15 1000 15 1 21 39", "1 14 1000 14 1 21 34", "1 13 1000 13 1 21 30", "1 12 1000 12 1 21 27", "1 11 1000 11 1 21 24", "1 10 1000 10 1 21 21", "1 9 1000 9 1 21 18", "1 8 1000 8 1 21 15", "1 7 1000 7 1 21 13", "1 6 1000 6 1 21 11", "1 5 1000 5 1 21 9", "1 4 1000 4 1 21 7", "1 3 1000 3 1 21 5", "1 2 1000 2 1 21 3"}
+;
+	  vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); 
+	LD _ = 837.0709015727234; 
+END
+CASE(5)
+	string stars_[] = {"8 7", "11 9"};
+	vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_)); 
+	string ships_[] = {"11 14 8 10 92 3 3", "12 14 12 6 434 4 6"};
+	  vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_)); 
+	LD _ = 0.01583636715715995; 
+END
+}
+// END CUT HERE

Index: TZTesterSp/template.cpp
==================================================================
--- TZTesterSp/template.cpp
+++ TZTesterSp/template.cpp
@@ -12,23 +12,17 @@
 #include <complex>
 #include <queue>
 #include <stack>
 #include <cmath>
 #include <cassert>
-#include <cstring>
-#ifdef __GNUC__
-#include <ext/hash_map>
-#define unordered_map __gnu_cxx::hash_map
-#else
-#include <unordered_map>
-#endif
 using namespace std;
 typedef long long LL;
-typedef complex<double> CMP;
+typedef long double LD;
+typedef complex<LD> CMP;
 
 class $CLASSNAME$ { public:
 	$RC$ $METHODNAME$($METHODPARMS$)
 	{
 	}
 };
 
 $TESTCODE$

ADDED   lib/geo/line_circle.cpp
Index: lib/geo/line_circle.cpp
==================================================================
--- lib/geo/line_circle.cpp
+++ lib/geo/line_circle.cpp
@@ -0,0 +1,14 @@
+typedef long double LD;
+typedef complex<LD> CMP;
+
+bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
+{
+	CMP v = (lb-la) / abs(lb-la);
+	CMP o = (c-la) / v;
+	if( abs(o.imag()) > r )
+		return false;
+	LD dx = sqrt(r*r - o.imag()*o.imag());
+	*p1 = la + (o.real()-dx)*v;
+	*p2 = la + (o.real()+dx)*v;
+	return true;
+}

Index: lib/graph/maxFlow.cpp
==================================================================
--- lib/graph/maxFlow.cpp
+++ lib/graph/maxFlow.cpp
@@ -9,10 +9,11 @@
 // Verified by
 //   - SRM 399 Div1 LV3
 //   - PKU 1459
 //   - CodeCraft 09 CUTS
 //   - SRM 465 Div1 LV2
+//   - SRM 543 Div1 LV3
 //-------------------------------------------------------------
 
 template<typename T>
 class IdGen
 {