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

Added SRM/634-U/1A.cpp version [9fbd3a306518e9ad]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +typedef complex<double> CMP;
           21  +
           22  +class ShoppingSurveyDiv1 { public:
           23  + int minValue(int N, int K, vector <int> s)
           24  + {
           25  +  for(int big=0; big<=N; ++big)
           26  +   if(can(N, K, s, big))
           27  +    return big;
           28  +
           29  +  assert(false);
           30  +  return -1;
           31  + }
           32  +
           33  + bool can(int N, int K, vector<int> sb, int BIG)
           34  + {
           35  +  sort(sb.rbegin(), sb.rend());
           36  +  assert(sb[K-1] >= BIG);
           37  +
           38  +  multiset<int, greater<int>> s;
           39  +  for(auto p: sb)
           40  +   if(p-BIG > 0)
           41  +    s.insert(p-BIG);
           42  +  int total = accumulate(s.begin(), s.end(), 0);
           43  +  if(total > (K-1)*(N-BIG))
           44  +   return false;
           45  +  if(!s.empty() && *s.begin() > (N-BIG))
           46  +   return false;
           47  +  return true;
           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 int& Expected, const int& 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(_, ShoppingSurveyDiv1().minValue(N, K, s));}
           65  +int main(){
           66  +
           67  +CASE(0)
           68  + int N = 10;
           69  + int K = 2;
           70  + int s_[] = {1, 2, 3};
           71  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
           72  + int _ = 0;
           73  +END
           74  +CASE(1)
           75  + int N = 5;
           76  + int K = 2;
           77  + int s_[] = {1, 2, 3};
           78  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
           79  + int _ = 1;
           80  +END
           81  +CASE(2)
           82  + int N = 4;
           83  + int K = 4;
           84  + int s_[] = {4, 4, 4, 2};
           85  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
           86  + int _ = 2;
           87  +END
           88  +CASE(3)
           89  + int N = 20;
           90  + int K = 3;
           91  + int s_[] = {1, 10, 3, 4, 8, 15, 3, 16, 18, 2, 7, 3};
           92  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
           93  + int _ = 10;
           94  +END
           95  +CASE(4)
           96  + int N = 4;
           97  + int K = 2;
           98  + int s_[] = {1, 2, 1, 1, 3, 1, 2, 2, 1, 2, 1};
           99  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
          100  + int _ = 2;
          101  +END
          102  +CASE(5)
          103  + int N = 2;
          104  + int K = 3;
          105  + int s_[] = {1, 1, 1, 2};
          106  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
          107  + int _ = 1;
          108  +END
          109  +CASE(6)
          110  + int N = 500;
          111  + int K = 1;
          112  + int s_[] = {500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500};
          113  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
          114  + int _ = -1;
          115  +END
          116  +CASE(6)
          117  + int N = 500;
          118  + int K = 500;
          119  + int s_[] = {500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500,500};
          120  +   vector <int> s(s_, s_+sizeof(s_)/sizeof(*s_));
          121  + int _ = -1;
          122  +END
          123  +}
          124  +// END CUT HERE

Added SRM/634-U/1B.cpp version [3a56668afe2cfe71]

            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 <tuple>
           18  +using namespace std;
           19  +typedef long long LL;
           20  +
           21  +template<typename T>
           22  +class IdGen
           23  +{
           24  + map<T, int> v2id_;
           25  + vector<T>   id2v_;
           26  +public:
           27  + int v2id(const T& v) {
           28  +  if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
           29  +  return v2id_[v];
           30  + }
           31  + const T& id2v(int i) const { return id2v_[i]; }
           32  + int size() const { return id2v_.size(); }
           33  +};
           34  +
           35  +template<typename Vert, typename Flow, int NV=2048>
           36  +class MaxFlow
           37  +{
           38  + IdGen<Vert> idgen;
           39  + vector<int> G[NV];
           40  + Flow F[NV][NV];
           41  +
           42  +public:
           43  + void addEdge( Vert s_, Vert t_, Flow f )
           44  + {
           45  +  const int s = idgen.v2id(s_), t = idgen.v2id(t_);
           46  +  G[s].push_back(t);
           47  +  G[t].push_back(s);
           48  +  F[s][t] = f;
           49  +  F[t][s] = 0;
           50  + }
           51  +
           52  + Flow calc( Vert s_, Vert t_ )
           53  + {
           54  +  const int S = idgen.v2id(s_), D = idgen.v2id(t_);
           55  +  for( Flow total=0 ;; ) {
           56  +   // Do BFS and compute the level for each node.
           57  +   int LV[NV] = {0};
           58  +   vector<int> Q(1, S);
           59  +   for(int lv=1; !Q.empty(); ++lv) {
           60  +    vector<int> Q2;
           61  +    for(size_t i=0; i!=Q.size(); ++i) {
           62  +     const vector<int>& ne = G[Q[i]];
           63  +     for(size_t j=0; j!=ne.size(); ++j)
           64  +      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
           65  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           66  +    }
           67  +    Q.swap(Q2);
           68  +   }
           69  +
           70  +   // Destination is now unreachable. Done.
           71  +   if( !LV[D] )
           72  +    return total;
           73  +
           74  +   // Iterating DFS.
           75  +   bool blocked[NV] = {};
           76  +   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           77  +  }
           78  + }
           79  +
           80  +private:
           81  + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
           82  + {
           83  +  Flow flow_out = 0;
           84  +  for(size_t i=0; i!=G[v].size(); ++i) {
           85  +   int u = G[v][i];
           86  +   if( LV[v]+1==LV[u] && F[v][u] ) {
           87  +    Flow f = min(flow_in-flow_out, F[v][u]);
           88  +    if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
           89  +     F[v][u]  -= f;
           90  +     F[u][v]  += f;
           91  +     flow_out += f;
           92  +     if( flow_in == flow_out ) return flow_out;
           93  +    }
           94  +   }
           95  +  }
           96  +  blocked[v] = (flow_out==0);
           97  +  return flow_out;
           98  + }
           99  +};
          100  +
          101  +
          102  +typedef complex<int> CMP;
          103  +double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); }
          104  +double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); }
          105  +int ccw(const CMP& a, CMP b, CMP c) {
          106  + b -= a; c -= a;
          107  + if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
          108  + if( outer_prod(b,c) < 0 ) return -1; // clockwise
          109  + if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line
          110  + if( norm(b) < norm(c) )   return -2; // [a--b]--c on line
          111  + return 0; // [a--c--b] on line
          112  +}
          113  +
          114  +bool cross(int x1, int y1, int x2, int y2,
          115  +           int X1, int Y1, int X2, int Y2) {
          116  + CMP p1(x1,y1);
          117  + CMP p2(x2,y2);
          118  + CMP P1(X1,Y1);
          119  + CMP P2(X2,Y2);
          120  + return ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0;
          121  +}
          122  +
          123  +class SegmentDrawing { public:
          124  + enum TAG {SRC, LEFT_R, RIGHT_R, LEFT_B, RIGHT_B, DST};
          125  + static const int INF = 0x3fffffff;
          126  +
          127  + int maxScore(vector <int> x, vector <int> y, vector <int> redScore, vector <int> blueScore)
          128  + {
          129  +  const int N = x.size();
          130  +
          131  +  vector<vector<bool>> cross_table(N*N, vector<bool>(N*N));
          132  +  for(int i=0; i<N; ++i)
          133  +  for(int k=i+1; k<N; ++k)
          134  +  for(int ii=0; ii<N; ++ii)
          135  +  for(int kk=ii+1; kk<N; ++kk)
          136  +   cross_table[i*N+k][ii*N+kk] = cross(x[i],y[i],x[k],y[k],x[ii],y[ii],x[kk],y[kk]);
          137  +
          138  +  auto* mf = new MaxFlow<pair<TAG,int>, LL>;
          139  +
          140  +  int all = 0;
          141  +  for(int i=0; i<N; ++i)
          142  +  for(int k=i+1; k<N; ++k) {
          143  +   int p = i*N + k;
          144  +   mf->addEdge(make_pair(SRC,0), make_pair(LEFT_R,p), redScore[p]);
          145  +   mf->addEdge(make_pair(LEFT_R,p), make_pair(RIGHT_R,p), INF);
          146  +   mf->addEdge(make_pair(RIGHT_R,p), make_pair(DST,0), 0);
          147  +   mf->addEdge(make_pair(SRC,0), make_pair(LEFT_B,p), 0);
          148  +   mf->addEdge(make_pair(LEFT_B,p), make_pair(RIGHT_B,p), INF);
          149  +   mf->addEdge(make_pair(RIGHT_B,p), make_pair(DST,0), blueScore[p]);
          150  +   all += redScore[p];
          151  +   all += blueScore[p];
          152  +  }
          153  +
          154  +  for(int i=0; i<N; ++i)
          155  +  for(int k=i+1; k<N; ++k)
          156  +  for(int ii=0; ii<N; ++ii)
          157  +  for(int kk=ii+1; kk<N; ++kk) {
          158  +   int rp = i*N + k;
          159  +   int bp = ii*N + kk;
          160  +   if(cross_table[rp][bp])
          161  +    mf->addEdge(make_pair(RIGHT_R,rp), make_pair(LEFT_B,bp), INF);
          162  +  }
          163  +
          164  +  LL flow = mf->calc(make_pair(SRC,0), make_pair(DST,0));
          165  +  delete mf;
          166  +  return all - flow;
          167  + }
          168  +};
          169  +
          170  +// BEGIN CUT HERE
          171  +#include <ctime>
          172  +double start_time; string timer()
          173  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          174  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          175  + { os << "{ ";
          176  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          177  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          178  +void verify_case(const int& Expected, const int& Received) {
          179  + bool ok = (Expected == Received);
          180  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          181  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          182  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          183  +#define END  verify_case(_, SegmentDrawing().maxScore(x, y, redScore, blueScore));}
          184  +int main(){
          185  +
          186  +CASE(0)
          187  + int x_[] = {0,1,0,-1};
          188  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          189  + int y_[] = {1,0,-1,0};
          190  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          191  + int redScore_[] = {0, 1, 2, 3,
          192  + 1, 0, 6, 4,
          193  + 2, 6, 0, 5,
          194  + 3, 4, 5, 0};
          195  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          196  + int blueScore_[] = {0, 2, 3, 7,
          197  + 2, 0, 4, 6,
          198  + 3, 4, 0, 5,
          199  + 7, 6, 5, 0};
          200  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          201  + int _ = 27;
          202  +END
          203  +CASE(1)
          204  + int x_[] = {0, 1};
          205  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          206  + int y_[] = {1, 0};
          207  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          208  + int redScore_[] = {0, 101, 101, 0};
          209  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          210  + int blueScore_[] = {0, 100, 100, 0};
          211  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          212  + int _ = 101;
          213  +END
          214  +CASE(2)
          215  + int x_[] = {-3, -1, -1,  1,  1,  3};
          216  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          217  + int y_[] = { 0, -2,  2, -2,  2,  0};
          218  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          219  + int redScore_[] = {0, 2, 1, 2, 1, 2,
          220  + 2, 0, 2, 1, 2, 1,
          221  + 1, 2, 0, 2, 1, 2,
          222  + 2, 1, 2, 0, 2, 1,
          223  + 1, 2, 1, 2, 0, 2,
          224  + 2, 1, 2, 1, 2, 0};
          225  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          226  + int blueScore_[] = {0, 0, 0, 0, 0, 0,
          227  + 0, 0, 0, 0, 0, 0,
          228  + 0, 0, 0, 21, 0, 0,
          229  + 0, 0, 21, 0, 0, 0,
          230  + 0, 0, 0, 0, 0, 0,
          231  + 0, 0, 0, 0, 0, 0};
          232  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          233  + int _ = 25;
          234  +END
          235  +CASE(3)
          236  + int x_[] = {-100, 100, 0, -10, 10, 0};
          237  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          238  + int y_[] = {0, 0, 100, 10, 10, 1};
          239  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          240  + int redScore_[] = { 0, 96, 96, 25, 25, 25,
          241  + 96,  0, 96, 25, 25, 25,
          242  + 96, 96,  0, 25, 25, 25,
          243  + 25, 25, 25,  0, 10, 10,
          244  + 25, 25, 25, 10,  0, 10,
          245  + 25, 25, 25, 10, 10,  0};
          246  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          247  + int blueScore_[] = { 0, 30, 30, 20, 20, 20,
          248  + 30,  0, 30, 20, 20, 20,
          249  + 30, 30,  0, 20, 20, 20,
          250  + 20, 20, 20,  0, 86, 86,
          251  + 20, 20, 20, 86,  0, 86,
          252  + 20, 20, 20, 86, 86,  0};
          253  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          254  + int _ = 546;
          255  +END
          256  +CASE(4)
          257  + int x_[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
          258  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          259  + int y_[] = {1, 4, 9, 16, 25, 36, 49, 64, 81, 100};
          260  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          261  + int redScore_[] = {0, 15, 2, 3, 4, 5, 6, 7, 8, 9,
          262  + 15, 0, 15, 2, 3, 4, 5, 6, 7, 8,
          263  + 2, 15, 0, 15, 2, 3, 4, 5, 6, 7,
          264  + 3, 2, 15, 0, 15, 2, 3, 4, 5, 6,
          265  + 4, 3, 2, 15, 0, 15, 2, 3, 4, 5,
          266  + 5, 4, 3, 2, 15, 0, 15, 2, 3, 4,
          267  + 6, 5, 4, 3, 2, 15, 0, 15, 2, 3,
          268  + 7, 6, 5, 4, 3, 2, 15, 0, 15, 2,
          269  + 8, 7, 6, 5, 4, 3, 2, 15, 0, 15,
          270  + 9, 8, 7, 6, 5, 4, 3, 2, 15, 0}
          271  +;
          272  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          273  + int blueScore_[] = {0, 0, 2, 3, 4, 5, 6, 7, 8, 9,
          274  + 0, 0, 0, 2, 3, 4, 5, 6, 7, 8,
          275  + 2, 0, 0, 0, 2, 3, 4, 5, 6, 7,
          276  + 3, 2, 0, 0, 0, 2, 3, 4, 5, 6,
          277  + 4, 3, 2, 0, 0, 100, 2, 3, 4, 5,
          278  + 5, 4, 3, 2, 100, 0, 0, 2, 3, 4,
          279  + 6, 5, 4, 3, 2, 0, 0, 0, 2, 3,
          280  + 7, 6, 5, 4, 3, 2, 0, 0, 0, 2,
          281  + 8, 7, 6, 5, 4, 3, 2, 0, 0, 0,
          282  + 9, 8, 7, 6, 5, 4, 3, 2, 0, 0};
          283  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          284  + int _ = 300;
          285  +END
          286  +/*
          287  +CASE(5)
          288  + int x_[] = ;
          289  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          290  + int y_[] = ;
          291  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          292  + int redScore_[] = ;
          293  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          294  + int blueScore_[] = ;
          295  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          296  + int _ = ;
          297  +END
          298  +CASE(6)
          299  + int x_[] = ;
          300  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          301  + int y_[] = ;
          302  +   vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_));
          303  + int redScore_[] = ;
          304  +   vector <int> redScore(redScore_, redScore_+sizeof(redScore_)/sizeof(*redScore_));
          305  + int blueScore_[] = ;
          306  +   vector <int> blueScore(blueScore_, blueScore_+sizeof(blueScore_)/sizeof(*blueScore_));
          307  + int _ = ;
          308  +END
          309  +*/
          310  +}
          311  +// END CUT HERE

Modified lib/geo/ccw.cpp from [81dbefbd30f15e79] to [bec880bc3280bac9].

    12     12    b -= a; c -= a;
    13     13    if( outer_prod(b,c) > 0 ) return +1; // counter clockwise
    14     14    if( outer_prod(b,c) < 0 ) return -1; // clockwise
    15     15    if( inner_prod(b,c) < 0 ) return +2; // c--[a--b] on line
    16     16    if( norm(b) < norm(c) )   return -2; // [a--b]--c on line
    17     17    return 0; // [a--c--b] on line
    18     18   }
           19  +
           20  +
           21  +// intersection of two line segments.
           22  +bool cross(CMP p1, CMP p2, CMP P1, CMP P2) {
           23  + return ccw(p1,p2,P1)*ccw(p1,p2,P2)<=0 && ccw(P1,P2,p1)*ccw(P1,P2,p2)<=0;
           24  +}