Overview
| SHA1 Hash: | e87d5512af248f9d509756dbdf44a2cdb5b30406 |
|---|---|
| Date: | 2011-06-03 13:52:02 |
| User: | kinaba |
| Comment: | 507, 508 |
| 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/507-U/1A.cpp version [4e5b4d79ecf48d8e]
> 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 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class CubeStickers { public: > 23 string isPossible(vector <string> sticker) > 24 { > 25 map<string,int> mp; > 26 for(int i=0; i<sticker.size(); ++i) > 27 mp[sticker[i]]++; > 28 int cnt = 0; > 29 for(map<string,int>::iterator it=mp.begin(); it!=mp.end(); ++it) > 30 cnt += min(2, it->second); > 31 return cnt>=6 ? "YES" : "NO"; > 32 } > 33 }; > 34 > 35 // BEGIN CUT HERE > 36 #include <ctime> > 37 double start_time; string timer() > 38 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 39 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 40 { os << "{ "; > 41 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 42 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 43 void verify_case(const string& Expected, const string& Received) { > 44 bool ok = (Expected == Received); > 45 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 46 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 47 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 48 #define END verify_case(_, CubeStickers().isPossible(sticker));} > 49 int main(){ > 50 > 51 CASE(0) > 52 string sticker_[] = {"cyan","magenta","yellow","purple","black","white", > 53 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 54 string _ = "YES"; > 55 END > 56 CASE(1) > 57 string sticker_[] = {"blue","blue","blue","blue","blue","blue","blue","b > 58 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 59 string _ = "NO"; > 60 END > 61 CASE(2) > 62 string sticker_[] = {"red","yellow","blue","red","yellow","blue","red"," > 63 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 64 string _ = "YES"; > 65 END > 66 CASE(3) > 67 string sticker_[] = {"purple","orange","orange","purple","black","orange > 68 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 69 string _ = "NO"; > 70 END > 71 CASE(4) > 72 string sticker_[] = {"white","gray","green","blue","yellow","red","targe > 73 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 74 string _ = "YES"; > 75 END > 76 /* > 77 CASE(5) > 78 string sticker_[] = ; > 79 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 80 string _ = ; > 81 END > 82 CASE(6) > 83 string sticker_[] = ; > 84 vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*st > 85 string _ = ; > 86 END > 87 */ > 88 } > 89 // END CUT HERE
Added SRM/507-U/1B.cpp version [9c730bac0778f4f4]
> 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 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class CubePacking { public: > 23 int getMinimumVolume(int Ns, int Nb, int L) > 24 { > 25 int m = L*L*L*Nb + Ns; > 26 int M = L*L*L*Nb + Ns + L*L; > 27 for(int c=m; c<=M; ++c) // <M should be fine, but just in case.. > 28 { > 29 for(int p=1; p*p*p<=c; ++p) if( c%p == 0 ) > 30 for(int q=p; p*q*q<=c; ++q) if( c/p%q == 0 ) > 31 { > 32 int r = c/p/q; > 33 int nL = (p/L)*(q/L)*(r/L); > 34 if( Nb <= nL ) > 35 return c; > 36 } > 37 } > 38 assert(false); > 39 return -1; > 40 } > 41 }; > 42 > 43 // BEGIN CUT HERE > 44 #include <ctime> > 45 double start_time; string timer() > 46 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 47 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 48 { os << "{ "; > 49 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 50 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 51 void verify_case(const int& Expected, const int& Received) { > 52 bool ok = (Expected == Received); > 53 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 54 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 55 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 56 #define END verify_case(_, CubePacking().getMinimumVolume(Ns, Nb, L));} > 57 int main(){ > 58 > 59 CASE(0) > 60 int Ns = 2; > 61 int Nb = 2; > 62 int L = 2; > 63 int _ = 20; > 64 END > 65 CASE(1) > 66 int Ns = 19; > 67 int Nb = 1; > 68 int L = 2; > 69 int _ = 27; > 70 END > 71 CASE(2) > 72 int Ns = 51; > 73 int Nb = 7; > 74 int L = 5; > 75 int _ = 950; > 76 END > 77 CASE(3) > 78 int Ns = 12345; > 79 int Nb = 987; > 80 int L = 10; > 81 int _ = 999400; > 82 END > 83 CASE(4) > 84 int Ns = 1000000000; > 85 int Nb = 1000000; > 86 int L = 10; > 87 int _ = -1; > 88 END > 89 CASE(5) > 90 int Ns = 1; > 91 int Nb = 1; > 92 int L = 1; > 93 int _ = 2; > 94 END > 95 CASE(5) > 96 int Ns = 1; > 97 int Nb = 1; > 98 int L = 2; > 99 int _ = 12; > 100 END > 101 > 102 } > 103 // END CUT HERE
Added SRM/507-U/1C-U.cpp version [58f85286182a4ca4]
> 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 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 static const int MODVAL = 1000000007; // must be prime for op/ > 23 struct mint > 24 { > 25 int val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(LL x):val(x%MODVAL) {} > 29 }; > 30 mint operator+(mint x, mint y) { return x.val+y.val; } > 31 mint operator*(mint x, mint y) { return LL(x.val)*y.val; } > 32 mint POW(mint x, int e) { > 33 mint v = 1; > 34 for(;e;x=x*x,e>>=1) > 35 if(e&1) > 36 v=v*x; > 37 return v; > 38 } > 39 mint operator/(mint x, mint y) { return x * POW(y, MODVAL-2); } > 40 vector<mint> FAC_(1,1); > 41 void FAC_INIT(int n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*int(F > 42 mint FAC(int x) { return FAC_[x]; } > 43 > 44 class CubeBuilding { public: > 45 int getCount(int R, int G, int B, int N) > 46 { > 47 FAC_INIT(25); > 48 memo2.assign(26*26*26*26, -1); > 49 memo2all.assign(26*26*26*26, -1); > 50 memo3.assign(26*26*26*26, -1); > 51 return (dim3(R,G,B,N,N)+dim3(G,B,R,N,N)+dim3(B,G,R,N,N)).val; > 52 } > 53 > 54 vector<int> memo3; > 55 mint dim3(int R, int G, int B, int n, int N) > 56 { > 57 if( n == 0 ) > 58 return (R+G+B==0 ? 1 : 0); > 59 > 60 if(G>B) swap(G,B); > 61 int key = ((R*26+G)*26+B)*26+n; > 62 if( memo3[key] >= 0 ) > 63 return memo3[key]; > 64 > 65 mint total = 0; > 66 for(int r=0; r<=R; ++r) > 67 for(int g=0; g<=G; ++g) > 68 for(int b=0; b<=B; ++b) > 69 total = total + dim2all(r,g,b,N)*dim3(R- > 70 memo3[key] = total.val; > 71 return total; > 72 } > 73 > 74 vector<int> memo2; > 75 mint dim2(int R, int G, int B, int n) > 76 { > 77 if( n == 0 ) return (R+G+B==0 ? 1 : 0); > 78 if( R == 0 ) return (G+B==0 ? 1 : 0); > 79 > 80 if(G>B) swap(G,B); > 81 int key = ((R*26+G)*26+B)*26+n; > 82 if( memo2[key] >= 0 ) > 83 return memo2[key]; > 84 > 85 mint total = 0; > 86 for(int r=1; r<=R; ++r) > 87 for(int g=0; g<=G; ++g) { > 88 int b = n-r-g; > 89 if( 0<=b && b<=B ) > 90 total = total + dim2all(R-r,G-g,B-b,n) * > 91 } > 92 memo2[key] = total.val; > 93 return total; > 94 } > 95 > 96 vector<int> memo2all; > 97 mint dim2all(int R, int G, int B, int n) > 98 { > 99 int key = ((R*26+G)*26+B)*26+n; > 100 if( memo2all[key] >= 0 ) > 101 return memo2all[key]; > 102 > 103 mint total = 0; > 104 for(int m=0; m<=n; ++m) > 105 total = total + dim2(R,G,B,m)*(FAC(n)/FAC(m)/FAC(n-m)); > 106 memo2all[key] = total.val; > 107 return total; > 108 } > 109 }; > 110 > 111 // BEGIN CUT HERE > 112 #include <ctime> > 113 double start_time; string timer() > 114 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 115 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 116 { os << "{ "; > 117 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 118 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 119 void verify_case(const int& Expected, const int& Received) { > 120 bool ok = (Expected == Received); > 121 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 122 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 123 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 124 #define END verify_case(_, CubeBuilding().getCount(R, G, B, N));} > 125 int main(){ > 126 > 127 CASE(0) > 128 int R = 1; > 129 int G = 0; > 130 int B = 1; > 131 int N = 2; > 132 int _ = 4; > 133 END > 134 CASE(1) > 135 int R = 1; > 136 int G = 1; > 137 int B = 2; > 138 int N = 1; > 139 int _ = 0; > 140 END > 141 CASE(2) > 142 int R = 2; > 143 int G = 2; > 144 int B = 1; > 145 int N = 3; > 146 int _ = 162; > 147 END > 148 CASE(3) > 149 int R = 0; > 150 int G = 0; > 151 int B = 10; > 152 int N = 12; > 153 int _ = 372185933; > 154 END > 155 CASE(4) > 156 int R = 25; > 157 int G = 25; > 158 int B = 25; > 159 int N = 25; > 160 int _ = -1; > 161 END > 162 /* > 163 CASE(5) > 164 int R = ; > 165 int G = ; > 166 int B = ; > 167 int N = ; > 168 int _ = ; > 169 END > 170 */ > 171 } > 172 // END CUT HERE
Added SRM/508-U/1A.cpp version [ecd23a1d05cecd15]
> 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 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class DivideAndShift { public: > 23 int getLeast(int N, int M) > 24 { > 25 --M; > 26 int best = 0x7fffffff; > 27 for(int d=1; d*d<=N; ++d) > 28 if( N%d == 0 ) > 29 { > 30 best = min(best, divStep(N/d)+shiftDist(M%d, d)) > 31 best = min(best, divStep(d)+shiftDist(M%(N/d), N > 32 } > 33 return best; > 34 } > 35 > 36 int shiftDist(int k, int P) > 37 { > 38 return min(k, P-k); > 39 } > 40 > 41 int divStep(int n) > 42 { > 43 int c = 0; > 44 for(int p=2; p*p<=n; ++p) > 45 while(n%p==0) {n/=p; ++c;} > 46 return c + (n>1); > 47 } > 48 }; > 49 > 50 // BEGIN CUT HERE > 51 #include <ctime> > 52 double start_time; string timer() > 53 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 54 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 55 { os << "{ "; > 56 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 57 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 58 void verify_case(const int& Expected, const int& Received) { > 59 bool ok = (Expected == Received); > 60 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 61 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 62 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 63 #define END verify_case(_, DivideAndShift().getLeast(N, M));} > 64 int main(){ > 65 > 66 CASE(0) > 67 int N = 56; > 68 int M = 14; > 69 int _ = 3; > 70 END > 71 CASE(1) > 72 int N = 49; > 73 int M = 5; > 74 int _ = 2; > 75 END > 76 CASE(2) > 77 int N = 256; > 78 int M = 7; > 79 int _ = 6; > 80 END > 81 CASE(3) > 82 int N = 6; > 83 int M = 1; > 84 int _ = 0; > 85 END > 86 CASE(4) > 87 int N = 77777; > 88 int M = 11111; > 89 int _ = 2; > 90 END > 91 CASE(5) > 92 int N = 1000000; > 93 int M = 1000000; > 94 int _ = -1; > 95 END > 96 CASE(6) > 97 int N = 1000000; > 98 int M = 999997; > 99 int _ = -1; > 100 END > 101 CASE(7) > 102 int N = 1; > 103 int M = 1; > 104 int _ = 0; > 105 END > 106 CASE(8) > 107 int N = 997*997; > 108 int M = 444; > 109 int _ = -1; > 110 END > 111 > 112 } > 113 // END CUT HERE
Added SRM/508-U/1B.cpp version [3d778b85bf6f47a5]
> 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 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class YetAnotherORProblem { public: > 23 map<vector<LL>, int> memo; > 24 int countSequences(const vector<LL>& R) > 25 { > 26 if( count(R.begin(),R.end(),0) == R.size() ) > 27 return 1; > 28 if( memo.count(R) ) > 29 return memo[R]; > 30 > 31 vector<LL> RR; > 32 for(int i=0; i<R.size(); ++i) > 33 RR.push_back(R[i]/2); > 34 > 35 int total = countSequences(RR); > 36 for(int i=0; i<R.size(); ++i) > 37 if( R[i] ) > 38 { > 39 if( (R[i]&1) == 0 ) RR[i]--; > 40 total = (total + countSequences(RR)) % 100000000 > 41 if( (R[i]&1) == 0 ) RR[i]++; > 42 } > 43 return memo[R] = total; > 44 } > 45 }; > 46 > 47 // BEGIN CUT HERE > 48 #include <ctime> > 49 double start_time; string timer() > 50 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 51 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 52 { os << "{ "; > 53 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 54 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 55 void verify_case(const int& Expected, const int& Received) { > 56 bool ok = (Expected == Received); > 57 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 58 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 59 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 60 #define END verify_case(_, YetAnotherORProblem().countSequences(R));} > 61 int main(){ > 62 > 63 CASE(0) > 64 long R_[] = {3,5}; > 65 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 66 int _ = 15; > 67 END > 68 CASE(1) > 69 long R_[] = {3,3,3}; > 70 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 71 int _ = 16; > 72 END > 73 CASE(2) > 74 long R_[] = {1,128}; > 75 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 76 int _ = 194; > 77 END > 78 CASE(3) > 79 long R_[] = {26,74,25,30}; > 80 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 81 int _ = 8409; > 82 END > 83 CASE(4) > 84 long R_[] = {1000000000,1000000000}; > 85 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 86 int _ = 420352509; > 87 END > 88 CASE(5) > 89 long long R_[] = {1000000000000000000LL,1000000000000000000LL,100000000000000000 > 90 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 91 int _ = -1; > 92 END > 93 CASE(6) > 94 long long R_[] = {1, 1}; > 95 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 96 int _ = 3; > 97 END > 98 CASE(6) > 99 long long R_[] = {0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xffffffffff > 100 vector<long long> R(R_, R_+sizeof(R_)/sizeof(*R_)); > 101 int _ = 3; > 102 END > 103 > 104 } > 105 // END CUT HERE
Added SRM/508-U/1C-U.cpp version [1ce44cdd43d689db]
> 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 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class BarbarianInvasion2 { public: > 23 double minimumTime(vector <int> boundaryX, vector <int> boundaryY, vecto > 24 { > 25 vector<CMP> b, c; > 26 for(int i=0; i<boundaryX.size(); ++i) > 27 b.push_back(CMP(boundaryX[i], boundaryY[i])); > 28 for(int i=0; i<cityX.size(); ++i) > 29 c.push_back(CMP(cityX[i], cityY[i])); > 30 > 31 double answer = 0; > 32 for(int i=0; i<b.size(); ++i) > 33 answer = max(answer, min_max(b[i], b[(i+1)%b.size()], c) > 34 return answer; > 35 } > 36 > 37 double min_max(CMP a, CMP b, vector<CMP> cs) > 38 { > 39 // return max[p on a-b] min[c in cs] |c-p| > 40 > 41 double factor = abs(b-a); > 42 { > 43 b -= a; > 44 for(int i=0; i<cs.size(); ++i) > 45 cs[i] -= a; > 46 for(int i=0; i<cs.size(); ++i) > 47 cs[i] /= b; > 48 } > 49 > 50 // return factor * max[p on 0-1] min[c in cs] |c-p| > 51 vector<double> ss; > 52 for(int i=0; i<cs.size(); ++i) > 53 for(int j=i+1; j<cs.size(); ++j) > 54 if( cs[i].real() != cs[j].real() ) > 55 ss.push_back( sectpoint(cs[i], cs[j]) ); > 56 sort(ss.begin(), ss.end()); > 57 double fmin_max = 0.0; > 58 > 59 double z = 0.0; > 60 for(int i=0; i<ss.size(); ++i) { > 61 double t = min(1.0, ss[i]); > 62 if( t > z ) { > 63 // [z, t) > 64 { > 65 double pt = (z+t)/2; > 66 int minK = 0; > 67 for(int k=1; k<cs.size(); ++k) > 68 if( abs(cs[minK]-pt) > abs(cs[k] > 69 minK = k; > 70 double fmin = furthest(z, t, cs[minK]); > 71 fmin_max = max(fmin_max, fmin); > 72 } > 73 z = t; > 74 } > 75 if( z>=1.0 ) > 76 break; > 77 } > 78 if( z < 1.0 ) { > 79 double t = 1.0; > 80 // [z, 1.0) > 81 { > 82 double pt = (z+t)/2; > 83 int minK = 0; > 84 for(int k=1; k<cs.size(); ++k) > 85 if( abs(cs[minK]-pt) > abs(cs[k]-pt) ) > 86 minK = k; > 87 double fmin = furthest(z, t, cs[minK]); > 88 fmin_max = max(fmin_max, fmin); > 89 } > 90 } > 91 cerr << factor*fmin_max << endl; > 92 return factor * fmin_max; > 93 } > 94 > 95 double sectpoint(CMP a, CMP b) > 96 { > 97 CMP c = (a+b)/2.0; > 98 CMP dir = (a-b)*CMP(0,1); > 99 dir /= abs(dir); > 100 return (c + c.imag() / dir.imag() * dir).real(); > 101 } > 102 > 103 double furthest(double a, double b, CMP c) > 104 { > 105 if( c.real() > (a+b)/2 ) > 106 return abs(c - a); > 107 else > 108 return abs(c - b); > 109 } > 110 }; > 111 > 112 // BEGIN CUT HERE > 113 #include <ctime> > 114 double start_time; string timer() > 115 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 116 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 117 { os << "{ "; > 118 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 119 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 120 void verify_case(const double& Expected, const double& Received) { > 121 bool ok = (abs(Expected - Received) < 1e-9); > 122 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 123 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 124 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 125 #define END verify_case(_, BarbarianInvasion2().minimumTime(boundaryX, boun > 126 int main(){ > 127 > 128 CASE(0) > 129 int boundaryX_[] = {0,2,2,0}; > 130 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 131 int boundaryY_[] = {0,0,2,2}; > 132 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 133 int cityX_[] = {1}; > 134 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 135 int cityY_[] = {1}; > 136 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 137 double _ = 1.414213562373088; > 138 END > 139 CASE(1) > 140 int boundaryX_[] = {0,3,3,0}; > 141 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 142 int boundaryY_[] = {0,0,3,3}; > 143 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 144 int cityX_[] = {1}; > 145 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 146 int cityY_[] = {1}; > 147 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 148 double _ = 2.8284271247461485; > 149 END > 150 CASE(2) > 151 int boundaryX_[] = {0,3,3,0}; > 152 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 153 int boundaryY_[] = {0,0,3,3}; > 154 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 155 int cityX_[] = {1,2}; > 156 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 157 int cityY_[] = {2,1}; > 158 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 159 double _ = 2.236067977499772; > 160 END > 161 CASE(3) > 162 int boundaryX_[] = {0,40,40,0}; > 163 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 164 int boundaryY_[] = {0,0,40,40}; > 165 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 166 int cityX_[] = {1,2,31,2,15}; > 167 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 168 int cityY_[] = {1,2,3,3,24}; > 169 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 170 double _ = 38.05748153551994; > 171 END > 172 CASE(4) > 173 int boundaryX_[] = {0,124,-6,-120,-300}; > 174 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 175 int boundaryY_[] = {0,125,140,137,-100}; > 176 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 177 int cityX_[] = {10,10,10,10}; > 178 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 179 int cityY_[] = {50,51,52,21}; > 180 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 181 double _ = 332.77770358002783; > 182 END > 183 /* > 184 CASE(5) > 185 int boundaryX_[] = ; > 186 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 187 int boundaryY_[] = ; > 188 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 189 int cityX_[] = ; > 190 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 191 int cityY_[] = ; > 192 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 193 double _ = ; > 194 END > 195 CASE(6) > 196 int boundaryX_[] = ; > 197 vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeo > 198 int boundaryY_[] = ; > 199 vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeo > 200 int cityX_[] = ; > 201 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 202 int cityY_[] = ; > 203 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 204 double _ = ; > 205 END > 206 */ > 207 } > 208 // END CUT HERE