Overview
| SHA1 Hash: | df56ee954dd365fcd0dcccdad7306aa668cb49ca |
|---|---|
| Date: | 2011-12-29 22:42:57 |
| User: | kinaba |
| Comment: | 528 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
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], > 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 > 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, > 64 tx->push_back( make_pair(t2, (func(x1,v1,t2)+func(x2,v2, > 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) > 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 > 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() > 90 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 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