0bad7aa887 2013-12-14 kinaba: #include <iostream> 0bad7aa887 2013-12-14 kinaba: #include <sstream> 0bad7aa887 2013-12-14 kinaba: #include <iomanip> 0bad7aa887 2013-12-14 kinaba: #include <vector> 0bad7aa887 2013-12-14 kinaba: #include <string> 0bad7aa887 2013-12-14 kinaba: #include <map> 0bad7aa887 2013-12-14 kinaba: #include <set> 0bad7aa887 2013-12-14 kinaba: #include <algorithm> 0bad7aa887 2013-12-14 kinaba: #include <numeric> 0bad7aa887 2013-12-14 kinaba: #include <iterator> 0bad7aa887 2013-12-14 kinaba: #include <functional> 0bad7aa887 2013-12-14 kinaba: #include <complex> 0bad7aa887 2013-12-14 kinaba: #include <queue> 0bad7aa887 2013-12-14 kinaba: #include <stack> 0bad7aa887 2013-12-14 kinaba: #include <cmath> 0bad7aa887 2013-12-14 kinaba: #include <cassert> 0bad7aa887 2013-12-14 kinaba: #include <tuple> 0bad7aa887 2013-12-14 kinaba: using namespace std; 0bad7aa887 2013-12-14 kinaba: typedef long long LL; 0bad7aa887 2013-12-14 kinaba: typedef complex<double> CMP; 0bad7aa887 2013-12-14 kinaba: 0bad7aa887 2013-12-14 kinaba: int gcd(int a, int b) 0bad7aa887 2013-12-14 kinaba: { 0bad7aa887 2013-12-14 kinaba: while(a) 0bad7aa887 2013-12-14 kinaba: swap(a, b%=a); 0bad7aa887 2013-12-14 kinaba: return b; 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: 0bad7aa887 2013-12-14 kinaba: class FindPolygons { public: 0bad7aa887 2013-12-14 kinaba: double minimumPolygon(int L) 0bad7aa887 2013-12-14 kinaba: { 0bad7aa887 2013-12-14 kinaba: if(L<=2) 0bad7aa887 2013-12-14 kinaba: return -1; 0bad7aa887 2013-12-14 kinaba: if(L%2==1) // euclid%2 == manhattan%2. tour is always even. 0bad7aa887 2013-12-14 kinaba: return -1; 0bad7aa887 2013-12-14 kinaba: 0bad7aa887 2013-12-14 kinaba: map<int, vector<pair<int,int>>> pyt; 0bad7aa887 2013-12-14 kinaba: for(int k=1; k<=L; ++k) { 0bad7aa887 2013-12-14 kinaba: auto& pk = pyt[k]; 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(0, k); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(k, 0); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(0, -k); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(-k, 0); 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: for(int m=1; m*m<=L/2; ++m) 0bad7aa887 2013-12-14 kinaba: for(int n=1; n<m && m*m+n*n<=L/2; ++n) 0bad7aa887 2013-12-14 kinaba: if(((m^n)&1) && gcd(m,n)==1) { 0bad7aa887 2013-12-14 kinaba: int a = m*m-n*n, b = 2*m*n, c = m*m+n*n; 0bad7aa887 2013-12-14 kinaba: for(int k=1; k*c<=L; ++k) { 0bad7aa887 2013-12-14 kinaba: auto& pk = pyt[k*c]; 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(k*a, k*b); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(k*a, -k*b); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(-k*a, k*b); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(-k*a, -k*b); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(k*b, k*a); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(k*b, -k*a); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(-k*b, k*a); 0bad7aa887 2013-12-14 kinaba: pk.emplace_back(-k*b, -k*a); 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: 0bad7aa887 2013-12-14 kinaba: // Triangle 0bad7aa887 2013-12-14 kinaba: int best = L; 0bad7aa887 2013-12-14 kinaba: for(int a=1; a*3<=L; ++a) 0bad7aa887 2013-12-14 kinaba: for(int b=a; a+b*2<=L; ++b) 0bad7aa887 2013-12-14 kinaba: { 0bad7aa887 2013-12-14 kinaba: int c = L-a-b; 0bad7aa887 2013-12-14 kinaba: 0bad7aa887 2013-12-14 kinaba: for(auto& av : pyt[a]) 0bad7aa887 2013-12-14 kinaba: { 0bad7aa887 2013-12-14 kinaba: int ax=av.first; 0bad7aa887 2013-12-14 kinaba: int ay=av.second; 0bad7aa887 2013-12-14 kinaba: if(ax>=0 && ay>=0) 0bad7aa887 2013-12-14 kinaba: for(auto& bv : pyt[b]) 0bad7aa887 2013-12-14 kinaba: { 0bad7aa887 2013-12-14 kinaba: int bx=bv.first; 0bad7aa887 2013-12-14 kinaba: int by=bv.second; 0bad7aa887 2013-12-14 kinaba: int cx=-ax-bx; 0bad7aa887 2013-12-14 kinaba: int cy=-ay-by; 0bad7aa887 2013-12-14 kinaba: if(ax*by!=ay*bx && cx*cx+cy*cy == c*c) { 0bad7aa887 2013-12-14 kinaba: best = min(best, c-a); 0bad7aa887 2013-12-14 kinaba: break; 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: if(best < L) 0bad7aa887 2013-12-14 kinaba: return best; 0bad7aa887 2013-12-14 kinaba: // Rectangle 0bad7aa887 2013-12-14 kinaba: if(L%4==0) 0bad7aa887 2013-12-14 kinaba: return 0; 0bad7aa887 2013-12-14 kinaba: return 1; 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: }; 0bad7aa887 2013-12-14 kinaba: 0bad7aa887 2013-12-14 kinaba: // BEGIN CUT HERE 0bad7aa887 2013-12-14 kinaba: #include <ctime> 0bad7aa887 2013-12-14 kinaba: double start_time; string timer() 0bad7aa887 2013-12-14 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 0bad7aa887 2013-12-14 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 0bad7aa887 2013-12-14 kinaba: { os << "{ "; 0bad7aa887 2013-12-14 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 0bad7aa887 2013-12-14 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 0bad7aa887 2013-12-14 kinaba: void verify_case(const double& Expected, const double& Received) { 0bad7aa887 2013-12-14 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 0bad7aa887 2013-12-14 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 0bad7aa887 2013-12-14 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 0bad7aa887 2013-12-14 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 0bad7aa887 2013-12-14 kinaba: #define END verify_case(_, FindPolygons().minimumPolygon(L));} 0bad7aa887 2013-12-14 kinaba: int main(){ 0bad7aa887 2013-12-14 kinaba: CASE(0) 0bad7aa887 2013-12-14 kinaba: int L = 4; 0bad7aa887 2013-12-14 kinaba: double _ = 0.0; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: CASE(1) 0bad7aa887 2013-12-14 kinaba: int L = 5; 0bad7aa887 2013-12-14 kinaba: double _ = -1.0; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: CASE(2) 0bad7aa887 2013-12-14 kinaba: int L = 12; 0bad7aa887 2013-12-14 kinaba: double _ = 2.0; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: CASE(3) 0bad7aa887 2013-12-14 kinaba: int L = 4984; 0bad7aa887 2013-12-14 kinaba: double _ = 819.0; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: CASE(4) 0bad7aa887 2013-12-14 kinaba: int L = 5000; 0bad7aa887 2013-12-14 kinaba: double _ = -999; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: CASE(4) 0bad7aa887 2013-12-14 kinaba: int L = 20; 0bad7aa887 2013-12-14 kinaba: double _ = -999; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: /* 0bad7aa887 2013-12-14 kinaba: CASE(5) 0bad7aa887 2013-12-14 kinaba: int L = ; 0bad7aa887 2013-12-14 kinaba: double _ = ; 0bad7aa887 2013-12-14 kinaba: END 0bad7aa887 2013-12-14 kinaba: */ 0bad7aa887 2013-12-14 kinaba: } 0bad7aa887 2013-12-14 kinaba: // END CUT HERE