• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

Added SRM/543/1A.cpp version [7b0052037b97ced1]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +#include <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class EllysXors { public:
           29  + long long getXor(long long L, long long R)
           30  + {
           31  +  if( R-L < 5 ) {
           32  +   LL a = 0;
           33  +   for(LL v=L; v<=R; ++v)
           34  +    a ^= v;
           35  +   return a;
           36  +  }
           37  +
           38  +  LL a = 0;
           39  +  if( L%2 == 1 ) {
           40  +   a ^= L;
           41  +   ++L;
           42  +  }
           43  +  if( R%2 == 0 ) {
           44  +   a ^= R;
           45  +   --R;
           46  +  }
           47  +  return a ^ ((R+1-L)/2%2);
           48  + }
           49  +};
           50  +
           51  +// BEGIN CUT HERE
           52  +#include <ctime>
           53  +double start_time; string timer()
           54  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           55  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           56  + { os << "{ ";
           57  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           58  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           59  +void verify_case(const long long& Expected, const long long& Received) {
           60  + bool ok = (Expected == Received);
           61  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           62  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           63  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           64  +#define END  verify_case(_, EllysXors().getXor(L, R));}
           65  +int main(){
           66  +
           67  +CASE(0)
           68  + long long L = 3LL;
           69  + long long R = 10LL;
           70  + long long _ = 8LL;
           71  +END
           72  +CASE(1)
           73  + long long L = 5LL;
           74  + long long R = 5LL;
           75  + long long _ = 5LL;
           76  +END
           77  +CASE(2)
           78  + long long L = 13LL;
           79  + long long R = 42LL;
           80  + long long _ = 39LL;
           81  +END
           82  +CASE(3)
           83  + long long L = 666LL;
           84  + long long R = 1337LL;
           85  + long long _ = 0LL;
           86  +END
           87  +CASE(4)
           88  + long long L = 1234567LL;
           89  + long long R = 89101112LL;
           90  + long long _ = 89998783LL;
           91  +END
           92  +/*
           93  +CASE(5)
           94  + long long L = LL;
           95  + long long R = LL;
           96  + long long _ = LL;
           97  +END
           98  +CASE(6)
           99  + long long L = LL;
          100  + long long R = LL;
          101  + long long _ = LL;
          102  +END
          103  +*/
          104  +}
          105  +// END CUT HERE

Added SRM/543/1B.cpp version [d73b3908d1719487]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +template<typename T>
           23  +struct DP2x
           24  +{
           25  + const int N1, N2;
           26  + vector<T> data;
           27  + DP2x(int, int N2, const T& t = T())
           28  +  : N1(2), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           29  + T& operator()(int i1, int i2)
           30  +  { i1&=1; return data[ (i1*N2)+i2 ]; }
           31  + void swap(DP2x& rhs)
           32  +  { data.swap(rhs.data); }
           33  +};
           34  +
           35  +class EllysRivers { public:
           36  + double getMin(int length, int walk, vector <int> width, vector <int> speed)
           37  + {
           38  +  DP2x<LD> dp(width.size()+1, length+1);
           39  +  for(int x=0; x<=length; ++x)
           40  +   dp(0,x) = x / LD(walk);
           41  +
           42  +  for(int y=1; y<=width.size(); ++y) {
           43  +   LD w = width[y-1];
           44  +   LD s = speed[y-1];
           45  +
           46  +   for(int x=length,px=length; x>=0; --x) {
           47  +   retry:
           48  +    LD t = dp(y-1, px) + sqrt(LD(px-x)*(px-x) + w*w) / s;
           49  +    if( px > 0 ) {
           50  +     LD tt = dp(y-1, px-1) + sqrt(LD(px-1-x)*(px-1-x) + w*w) / s;
           51  +     if( tt < t ) {
           52  +      --px;
           53  +      goto retry;
           54  +     }
           55  +    }
           56  +    dp(y, x) = t;
           57  +   }
           58  +  }
           59  +
           60  +  return dp(width.size(), length);
           61  + }
           62  +};
           63  +
           64  +// BEGIN CUT HERE
           65  +#include <ctime>
           66  +LD start_time; string timer()
           67  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           68  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           69  + { os << "{ ";
           70  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           71  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           72  +void verify_case(const LD& Expected, const LD& Received) {
           73  + bool ok = (abs(Expected - Received) < 1e-9);
           74  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           75  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           76  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           77  +#define END  verify_case(_, EllysRivers().getMin(length, walk, width, speed));}
           78  +int main(){
           79  +
           80  +CASE(0)
           81  + int length = 10;
           82  + int walk = 3;
           83  + int width_[] = {5, 2, 3};
           84  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
           85  + int speed_[] = {5, 2, 7};
           86  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
           87  + LD _ = 3.231651964071508;
           88  +END
           89  +CASE(1)
           90  + int length = 10000;
           91  + int walk = 211;
           92  + int width_[] = {911};
           93  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
           94  + int speed_[] = {207};
           95  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
           96  + LD _ = 48.24623664712219;
           97  +END
           98  +CASE(2)
           99  + int length = 1337;
          100  + int walk = 2;
          101  + int width_[] = {100, 200, 300, 400};
          102  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
          103  + int speed_[] = {11, 12, 13, 14};
          104  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
          105  + LD _ = 128.57830549575695;
          106  +END
          107  +CASE(3)
          108  + int length = 77;
          109  + int walk = 119;
          110  + int width_[] = {11, 12, 13, 14};
          111  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
          112  + int speed_[] = {100, 200, 300, 400};
          113  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
          114  + LD _ = 0.3842077071089629;
          115  +END
          116  +CASE(4)
          117  + int length = 7134;
          118  + int walk = 1525;
          119  + int width_[] = {11567, 19763, 11026, 10444, 24588, 22263, 17709, 11181, 15292, 28895, 15039, 18744, 19985, 13795, 26697, 18812, 25655, 13620, 28926, 12393};
          120  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
          121  + int speed_[] = {1620, 1477, 2837, 2590, 1692, 2270, 1655, 1078, 2683, 1475, 1383, 1153, 1862, 1770, 1671, 2318, 2197, 1768, 1979, 1057};
          122  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
          123  + LD _ = 214.6509731258811;
          124  +END
          125  +CASE(5)
          126  + int length = 100000;
          127  + int walk = 1;
          128  + int width_[] = {1000000, 1000000, 1000000};
          129  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
          130  + int speed_[] = {1, 1000000, 1};
          131  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
          132  + LD _ = 2000001.004987562;
          133  +END
          134  +CASE(6)
          135  + int length = 100000;
          136  + int walk = 1;
          137  + int width_[] = {1000000, 1000000, 1000000};
          138  +   vector <int> width(width_, width_+sizeof(width_)/sizeof(*width_));
          139  + int speed_[] = {1000000, 1000000, 1};
          140  +   vector <int> speed(speed_, speed_+sizeof(speed_)/sizeof(*speed_));
          141  + LD _ = 1000002.0024984397;
          142  +END
          143  +}
          144  +// END CUT HERE

Added SRM/543/1C.cpp version [978635090b60953d]

            1  +#include <iostream>
            2  +#include <sstream>
            3  +#include <iomanip>
            4  +#include <vector>
            5  +#include <string>
            6  +#include <map>
            7  +#include <set>
            8  +#include <algorithm>
            9  +#include <numeric>
           10  +#include <iterator>
           11  +#include <functional>
           12  +#include <complex>
           13  +#include <queue>
           14  +#include <stack>
           15  +#include <cmath>
           16  +#include <cassert>
           17  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +struct Ship {
           23  + CMP s, e;
           24  + LD speed;
           25  + LD r;
           26  + LD energy;
           27  +};
           28  +
           29  +template<typename T>
           30  +class IdGen
           31  +{
           32  + map<T, int> v2id_;
           33  + vector<T>   id2v_;
           34  +public:
           35  + int v2id(const T& v) {
           36  +  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
           37  +  return v2id_[v];
           38  + }
           39  + const T& id2v(int i) const { return id2v_[i]; }
           40  + int size() const { return id2v_.size(); }
           41  +};
           42  +
           43  +template<typename Vert, typename Flow, int NV=512>
           44  +class MaxFlow
           45  +{
           46  + IdGen<Vert> idgen;
           47  + vector<int> G[NV];
           48  + Flow F[NV][NV];
           49  +
           50  +public:
           51  + void addEdge( Vert s_, Vert t_, Flow f )
           52  + {
           53  +  const int s = idgen.v2id(s_), t = idgen.v2id(t_);
           54  +  G[s].push_back(t);
           55  +  G[t].push_back(s);
           56  +  F[s][t] = f;
           57  +  F[t][s] = 0;
           58  + }
           59  +
           60  + Flow calc( Vert s_, Vert t_ )
           61  + {
           62  +  const int S = idgen.v2id(s_), D = idgen.v2id(t_);
           63  +  for( Flow total=0 ;; ) {
           64  +   // Do BFS and compute the level for each node.
           65  +   int LV[NV] = {0};
           66  +   vector<int> Q(1, S);
           67  +   for(int lv=1; !Q.empty(); ++lv) {
           68  +    vector<int> Q2;
           69  +    for(size_t i=0; i!=Q.size(); ++i) {
           70  +     const vector<int>& ne = G[Q[i]];
           71  +     for(size_t j=0; j!=ne.size(); ++j)
           72  +      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
           73  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           74  +    }
           75  +    Q.swap(Q2);
           76  +   }
           77  +
           78  +   // Destination is now unreachable. Done.
           79  +   if( !LV[D] )
           80  +    return total;
           81  +
           82  +   // Iterating DFS.
           83  +   bool blocked[NV] = {};
           84  +   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           85  +  }
           86  + }
           87  +
           88  +private:
           89  + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
           90  + {
           91  +  Flow flow_out = 0;
           92  +  for(size_t i=0; i!=G[v].size(); ++i) {
           93  +   int u = G[v][i];
           94  +   if( LV[v]+1==LV[u] && F[v][u] ) {
           95  +    Flow f = min(flow_in-flow_out, F[v][u]);
           96  +    if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
           97  +     F[v][u]  -= f;
           98  +     F[u][v]  += f;
           99  +     flow_out += f;
          100  +     if( flow_in == flow_out ) return flow_out;
          101  +    }
          102  +   }
          103  +  }
          104  +  blocked[v] = (flow_out==0);
          105  +  return flow_out;
          106  + }
          107  +};
          108  +
          109  +bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
          110  +{
          111  + CMP v = (lb-la) / abs(lb-la);
          112  + CMP o = (c-la) / v;
          113  + if( abs(o.imag()) > r )
          114  +  return false;
          115  + LD dx = sqrt(r*r - o.imag()*o.imag());
          116  + *p1 = la + (o.real()-dx)*v;
          117  + *p2 = la + (o.real()+dx)*v;
          118  + return true;
          119  +}
          120  +
          121  +class EllysDeathStars { public:
          122  + double getMax(vector <string> stars_, vector <string> ships_)
          123  + {
          124  +  vector<CMP> stars;
          125  +  for(int i=0; i<stars_.size(); ++i)
          126  +  {
          127  +   stringstream sin(stars_[i]);
          128  +   int x, y;
          129  +   sin >> x >> y;
          130  +   stars.push_back(CMP(x,y));
          131  +  }
          132  +  vector<Ship> ships;
          133  +  for(int i=0; i<ships_.size(); ++i)
          134  +  {
          135  +   stringstream sin(ships_[i]);
          136  +   int sx, sy, ex, ey, s, r, e;
          137  +   sin >> sx >> sy >> ex >> ey >> s >> r >> e;
          138  +   Ship ship;
          139  +   ship.s = CMP(sx,sy);
          140  +   ship.e = CMP(ex,ey);
          141  +   if(ship.s == ship.e)
          142  +    continue;
          143  +   ship.speed = s;
          144  +   ship.r = r;
          145  +   ship.energy = e;
          146  +   ships.push_back(ship);
          147  +  }
          148  +  return solve(stars, ships);
          149  + }
          150  +
          151  + LD solve(const vector<CMP>& stars, const vector<Ship>& ships)
          152  + {
          153  +  typedef pair<int, int> Vert;
          154  +  MaxFlow<Vert, LD, 2048>* mf = new MaxFlow<Vert, LD, 2048>();
          155  +  for(int b=0; b<ships.size(); ++b)
          156  +   mf->addEdge(Vert(0,0), Vert(1,b), ships[b].energy);
          157  +
          158  +  int id = 0;
          159  +  for(int a=0; a<stars.size(); ++a) {
          160  +   vector<LD> events;
          161  +   events.push_back(0);
          162  +   for(int b=0; b<ships.size(); ++b)
          163  +    events.push_back(abs(ships[b].e-ships[b].s) / ships[b].speed);
          164  +   LD lasttime = *max_element(events.begin(), events.end());
          165  +
          166  +   for(int b=0; b<ships.size(); ++b) {
          167  +    CMP p = ships[b].s;
          168  +    CMP q = ships[b].e;
          169  +    CMP o = stars[a];
          170  +    LD r = ships[b].r;
          171  +    LD speed = ships[b].speed;
          172  +
          173  +    o = (o - p) / ((q-p) / abs(q-p));
          174  +    LD y = abs(o.imag());
          175  +    if( y < r ) {
          176  +     LD dx = sqrt(r*r - y*y);
          177  +     LD x1 = o.real() - dx;
          178  +     LD x2 = o.real() + dx;
          179  +     if(0<x1/speed && x1/speed<lasttime)
          180  +      events.push_back( x1 / speed );
          181  +     if(0<x2/speed && x2/speed<lasttime)
          182  +      events.push_back( x2 / speed );
          183  +    }
          184  +   }
          185  +   sort(events.begin(), events.end());
          186  +
          187  +   for(int i=0; i+1<events.size(); ++i, ++id) {
          188  +    LD sec = events[i+1] - events[i];
          189  +    LD mid = (events[i+1] + events[i]) / 2;
          190  +    for(int b=0; b<ships.size(); ++b) {
          191  +     LD rng = abs(ships[b].e - ships[b].s) / ships[b].speed;
          192  +     CMP pos = ships[b].s + (ships[b].e-ships[b].s)/abs(ships[b].e-ships[b].s)*ships[b].speed*mid;
          193  +     if( 0<mid && mid<rng && abs(pos-stars[a])<ships[b].r)
          194  +      mf->addEdge(Vert(1,b), Vert(2,id), sec);
          195  +    }
          196  +    mf->addEdge(Vert(2,id), Vert(3,0), sec);
          197  +   }
          198  +  }
          199  +
          200  +  LD flow = mf->calc(Vert(0,0), Vert(3,0));
          201  +  delete mf;
          202  +  return flow;
          203  + }
          204  +};
          205  +
          206  +// BEGIN CUT HERE
          207  +#include <ctime>
          208  +LD start_time; string timer()
          209  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          210  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          211  + { os << "{ ";
          212  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          213  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          214  +void verify_case(const LD& Expected, const LD& Received) {
          215  + bool ok = (abs(Expected - Received) < 1e-9);
          216  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          217  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          218  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          219  +#define END  verify_case(_, EllysDeathStars().getMax(stars, ships));}
          220  +int main(){
          221  +
          222  +CASE(0)
          223  + string stars_[] = {"2 2"};
          224  +   vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
          225  + string ships_[] = {"1 1 5 3 2 1 2"};
          226  +   vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
          227  + LD _ = 0.894427190999916;
          228  +END
          229  +CASE(1)
          230  + string stars_[] = {"12 10", "7 5"};
          231  +   vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
          232  + 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"};
          233  +   vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
          234  + LD _ = 4.983770744659944;
          235  +END
          236  +CASE(2)
          237  + string stars_[] = {"5 77", "60 50", "10 46", "22 97", "87 69"};
          238  +   vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
          239  + string ships_[] = {"42 17 66 11 5 7 13", "10 10 20 20 3 3 3", "13 15 18 9 4 1 2",
          240  + "99 71 63 81 19 4 60", "27 34 56 43 11 3 12"};
          241  +   vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
          242  + LD _ = 0.0;
          243  +END
          244  +CASE(3)
          245  + string stars_[] = {"141 393", "834 847", "568 43", "18 228", "515 794",
          246  + "167 283", "849 333", "719 738", "434 261", "613 800",
          247  + "127 340", "466 938", "598 601"};
          248  +   vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
          249  + string ships_[] = {"410 951 472 100 337 226 210", "713 352 677 908 731 687 300",
          250  + "191 41 337 92 446 716 213", "598 889 446 907 148 650 203",
          251  + "168 556 470 924 344 369 198", "300 182 350 936 737 533 45",
          252  + "410 871 488 703 746 631 80", "270 777 636 539 172 103 56",
          253  + "466 906 522 98 693 77 309", "768 698 846 110 14 643 14",
          254  + "755 724 664 465 263 759 120"};
          255  +   vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
          256  + LD _ = 31.965770956316362;
          257  +END
          258  +CASE(4)
          259  + string stars_[] =
          260  +{"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"}
          261  +;
          262  +   vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
          263  + string ships_[] =
          264  +  {"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"}
          265  +;
          266  +   vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
          267  + LD _ = 837.0709015727234;
          268  +END
          269  +CASE(5)
          270  + string stars_[] = {"8 7", "11 9"};
          271  + vector <string> stars(stars_, stars_+sizeof(stars_)/sizeof(*stars_));
          272  + string ships_[] = {"11 14 8 10 92 3 3", "12 14 12 6 434 4 6"};
          273  +   vector <string> ships(ships_, ships_+sizeof(ships_)/sizeof(*ships_));
          274  + LD _ = 0.01583636715715995;
          275  +END
          276  +}
          277  +// END CUT HERE

Modified TZTesterSp/template.cpp from [56e8b77f261a915b] to [6e30a998ce576012].

    10     10   #include <iterator>
    11     11   #include <functional>
    12     12   #include <complex>
    13     13   #include <queue>
    14     14   #include <stack>
    15     15   #include <cmath>
    16     16   #include <cassert>
    17         -#include <cstring>
    18         -#ifdef __GNUC__
    19         -#include <ext/hash_map>
    20         -#define unordered_map __gnu_cxx::hash_map
    21         -#else
    22         -#include <unordered_map>
    23         -#endif
    24     17   using namespace std;
    25     18   typedef long long LL;
    26         -typedef complex<double> CMP;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
    27     21   
    28     22   class $CLASSNAME$ { public:
    29     23    $RC$ $METHODNAME$($METHODPARMS$)
    30     24    {
    31     25    }
    32     26   };
    33     27   
    34     28   $TESTCODE$

Added lib/geo/line_circle.cpp version [0f1f35288c2dfafe]

            1  +typedef long double LD;
            2  +typedef complex<LD> CMP;
            3  +
            4  +bool line_circle(CMP la, CMP lb, CMP c, LD r, CMP* p1, CMP* p2)
            5  +{
            6  + CMP v = (lb-la) / abs(lb-la);
            7  + CMP o = (c-la) / v;
            8  + if( abs(o.imag()) > r )
            9  +  return false;
           10  + LD dx = sqrt(r*r - o.imag()*o.imag());
           11  + *p1 = la + (o.real()-dx)*v;
           12  + *p2 = la + (o.real()+dx)*v;
           13  + return true;
           14  +}

Modified lib/graph/maxFlow.cpp from [296b9275312ebbf1] to [6a23b64e61d31ffb].

     7      7   // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0
     8      8   //
     9      9   // Verified by
    10     10   //   - SRM 399 Div1 LV3
    11     11   //   - PKU 1459
    12     12   //   - CodeCraft 09 CUTS
    13     13   //   - SRM 465 Div1 LV2
           14  +//   - SRM 543 Div1 LV3
    14     15   //-------------------------------------------------------------
    15     16   
    16     17   template<typename T>
    17     18   class IdGen
    18     19   {
    19     20    map<T, int> v2id_;
    20     21    vector<T>   id2v_;