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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 46 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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","purple"}; 53 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 54 + string _ = "YES"; 55 +END 56 +CASE(1) 57 + string sticker_[] = {"blue","blue","blue","blue","blue","blue","blue","blue","blue","blue"}; 58 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 59 + string _ = "NO"; 60 +END 61 +CASE(2) 62 + string sticker_[] = {"red","yellow","blue","red","yellow","blue","red","yellow","blue"}; 63 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 64 + string _ = "YES"; 65 +END 66 +CASE(3) 67 + string sticker_[] = {"purple","orange","orange","purple","black","orange","purple"}; 68 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 69 + string _ = "NO"; 70 +END 71 +CASE(4) 72 + string sticker_[] = {"white","gray","green","blue","yellow","red","target","admin"}; 73 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 74 + string _ = "YES"; 75 +END 76 +/* 77 +CASE(5) 78 + string sticker_[] = ; 79 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 80 + string _ = ; 81 +END 82 +CASE(6) 83 + string sticker_[] = ; 84 + vector <string> sticker(sticker_, sticker_+sizeof(sticker_)/sizeof(*sticker_)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 54 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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(FAC_.size()) ); } 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-r,G-g,B-b,n-1,N); 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) * (FAC(n-1)/FAC(r-1)/FAC(g)/FAC(b)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 122 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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/d)); 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 61 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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)) % 1000000009; 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 58 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL,1000000000000000000LL}; 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, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, 0xfffffffffffffffLL, }; 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, vector <int> cityX, vector <int> cityY) 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]-pt) ) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 123 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 124 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 125 +#define END verify_case(_, BarbarianInvasion2().minimumTime(boundaryX, boundaryY, cityX, cityY));} 126 +int main(){ 127 + 128 +CASE(0) 129 + int boundaryX_[] = {0,2,2,0}; 130 + vector <int> boundaryX(boundaryX_, boundaryX_+sizeof(boundaryX_)/sizeof(*boundaryX_)); 131 + int boundaryY_[] = {0,0,2,2}; 132 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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_)/sizeof(*boundaryX_)); 142 + int boundaryY_[] = {0,0,3,3}; 143 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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_)/sizeof(*boundaryX_)); 153 + int boundaryY_[] = {0,0,3,3}; 154 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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_)/sizeof(*boundaryX_)); 164 + int boundaryY_[] = {0,0,40,40}; 165 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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_)/sizeof(*boundaryX_)); 175 + int boundaryY_[] = {0,125,140,137,-100}; 176 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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_)/sizeof(*boundaryX_)); 187 + int boundaryY_[] = ; 188 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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_)/sizeof(*boundaryX_)); 198 + int boundaryY_[] = ; 199 + vector <int> boundaryY(boundaryY_, boundaryY_+sizeof(boundaryY_)/sizeof(*boundaryY_)); 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