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

Added SRM/528/2C.cpp version [ce0cb27aa1496b82]

            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 Mosquitoes { public:
           29  + int getMaximum(vector <int> xInit, vector <int> v, int R)
           30  + {
           31  +  vector< pair<double,double> > tx;
           32  +  for (int i = 0; i < xInit.size(); i++)
           33  +   for (int j = i+1; j < xInit.size(); j++)
           34  +    critical_points(xInit[i], v[i], xInit[j], v[j], R, &tx);
           35  +
           36  +  int best = 1;
           37  +  for(int i=0; i<tx.size(); ++i) {
           38  +   double t = tx[i].first;
           39  +   double x = tx[i].second;
           40  +   if( t >= 0 ) {
           41  +    int cnt = 0;
           42  +    for (int k = 0; k < xInit.size(); k++)
           43  +     if( is_in(xInit[k], v[k], t, x, R) )
           44  +      ++cnt;
           45  +    best = max(best, cnt);
           46  +   }
           47  +  }
           48  +  return best;
           49  + }
           50  +
           51  + void critical_points(double x1, double v1, double x2, double v2, double R,
           52  +  vector< pair<double,double> >* tx)
           53  + {
           54  +  // Compute t such that | (x1 + t v1) - (x2 - t v2) | = 2R
           55  +  double x = x1 - x2;
           56  +  double v = v1 - v2;
           57  +  if( v == 0 ) {
           58  +   if( abs(x) <= 2*R )
           59  +    tx->push_back( make_pair(0, (x1+x2)/2) );
           60  +  } else {
           61  +   double t1 = (2*R - x) / v;
           62  +   double t2 = (2*R + x) / (-v);
           63  +   tx->push_back( make_pair(t1, (func(x1,v1,t1)+func(x2,v2,t1))/2) );
           64  +   tx->push_back( make_pair(t2, (func(x1,v1,t2)+func(x2,v2,t2))/2) );
           65  +  }
           66  + }
           67  +
           68  + double func(double x, double v, double t)
           69  + {
           70  +  return x + v*t;
           71  + }
           72  +
           73  + bool is_in(double x, double v, double t, double c, double R)
           74  + {
           75  +  return abs(func(x,v,t) - c) <= R + 1e-8;
           76  + }
           77  +};
           78  +
           79  +// BEGIN CUT HERE
           80  +#include <ctime>
           81  +double start_time; string timer()
           82  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           83  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           84  + { os << "{ ";
           85  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           86  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           87  +void verify_case(const int& Expected, const int& Received) {
           88  + bool ok = (Expected == Received);
           89  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           90  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           91  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           92  +#define END  verify_case(_, Mosquitoes().getMaximum(xInit, v, R));}
           93  +int main(){
           94  +
           95  +CASE(0)
           96  + int xInit_[] = {1, -1};
           97  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
           98  + int v_[] = {1, -1};
           99  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          100  + int R = 10;
          101  + int _ = 2;
          102  +END
          103  +CASE(1)
          104  + int xInit_[] = {100, -100};
          105  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
          106  + int v_[] = {1, -1};
          107  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          108  + int R = 10;
          109  + int _ = 1;
          110  +END
          111  +CASE(2)
          112  + int xInit_[] = {0, -1, 10, -11, 99, -99};
          113  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
          114  + int v_[] = {1, -1, -3, 3, 47, -47};
          115  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          116  + int R = 3;
          117  + int _ = 4;
          118  +END
          119  +CASE(3)
          120  + int xInit_[] = {5};
          121  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
          122  + int v_[] = {2};
          123  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          124  + int R = 8;
          125  + int _ = 1;
          126  +END
          127  +CASE(4)
          128  + int xInit_[] = {12,34,56,78,90};
          129  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
          130  + int v_[] = {-1,2,-3,4,-5};
          131  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          132  + int R = 6;
          133  + int _ = 3;
          134  +END
          135  +CASE(5)
          136  + int xInit_[] = {-29, -27};
          137  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
          138  + int v_[] = {25, 61};
          139  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          140  + int R = 7;
          141  + int _ = 2;
          142  +END
          143  +/*
          144  +CASE(6)
          145  + int xInit_[] = ;
          146  +   vector <int> xInit(xInit_, xInit_+sizeof(xInit_)/sizeof(*xInit_));
          147  + int v_[] = ;
          148  +   vector <int> v(v_, v_+sizeof(v_)/sizeof(*v_));
          149  + int R = ;
          150  + int _ = ;
          151  +END
          152  +*/
          153  +}
          154  +// END CUT HERE