4fd800b3a8 2011-02-23 kinaba: #include <iostream> 4fd800b3a8 2011-02-23 kinaba: #include <sstream> 4fd800b3a8 2011-02-23 kinaba: #include <iomanip> 4fd800b3a8 2011-02-23 kinaba: #include <vector> 4fd800b3a8 2011-02-23 kinaba: #include <string> 4fd800b3a8 2011-02-23 kinaba: #include <map> 4fd800b3a8 2011-02-23 kinaba: #include <set> 4fd800b3a8 2011-02-23 kinaba: #include <algorithm> 4fd800b3a8 2011-02-23 kinaba: #include <numeric> 4fd800b3a8 2011-02-23 kinaba: #include <iterator> 4fd800b3a8 2011-02-23 kinaba: #include <functional> 4fd800b3a8 2011-02-23 kinaba: #include <complex> 4fd800b3a8 2011-02-23 kinaba: #include <queue> 4fd800b3a8 2011-02-23 kinaba: #include <stack> 4fd800b3a8 2011-02-23 kinaba: #include <cmath> 4fd800b3a8 2011-02-23 kinaba: #include <cassert> 4fd800b3a8 2011-02-23 kinaba: #include <cstring> 4fd800b3a8 2011-02-23 kinaba: using namespace std; 4fd800b3a8 2011-02-23 kinaba: typedef long long LL; 4fd800b3a8 2011-02-23 kinaba: typedef complex<double> CMP; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double outer_prod(const CMP& a, const CMP& b) { return imag(conj(a)*b); } 4fd800b3a8 2011-02-23 kinaba: double inner_prod(const CMP& a, const CMP& b) { return real(conj(a)*b); } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: int ccw(const CMP& a, CMP b, CMP c) { 4fd800b3a8 2011-02-23 kinaba: b -= a; c -= a; 4fd800b3a8 2011-02-23 kinaba: if( outer_prod(b,c) > 0 ) return +1; // counter clockwise 4fd800b3a8 2011-02-23 kinaba: if( outer_prod(b,c) < 0 ) return -1; // clockwise 4fd800b3a8 2011-02-23 kinaba: if( inner_prod(b,c) < 0 ) return +2; // c--a--b on line 4fd800b3a8 2011-02-23 kinaba: if( norm(b) < norm(c) ) return -2; // a--b--c on line 4fd800b3a8 2011-02-23 kinaba: return 0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: bool byX( const CMP& a, const CMP& b ) { 4fd800b3a8 2011-02-23 kinaba: if( a.real() != b.real() ) 4fd800b3a8 2011-02-23 kinaba: return a.real() < b.real(); 4fd800b3a8 2011-02-23 kinaba: return a.imag() < b.imag(); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<CMP> convex_hull( vector<CMP> p ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: #define IS_RIGHT <0 // skip on-line verts 4fd800b3a8 2011-02-23 kinaba: //#define IS_RIGHT ==-1 // take all 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: sort(p.begin(), p.end(), &byX); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<CMP> ans; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<p.size(); ans.push_back(p[i++])) // left-to-right 4fd800b3a8 2011-02-23 kinaba: while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT ) 4fd800b3a8 2011-02-23 kinaba: ans.pop_back(); 4fd800b3a8 2011-02-23 kinaba: if( ans.size() == p.size() ) 4fd800b3a8 2011-02-23 kinaba: return ans; 4fd800b3a8 2011-02-23 kinaba: for(int i=p.size()-2; i>=0; ans.push_back(p[i--])) // right-to-left 4fd800b3a8 2011-02-23 kinaba: while( ans.size()>=2 && ccw(ans[ans.size()-2], ans[ans.size()-1], p[i]) IS_RIGHT ) 4fd800b3a8 2011-02-23 kinaba: ans.pop_back(); 4fd800b3a8 2011-02-23 kinaba: ans.pop_back(); 4fd800b3a8 2011-02-23 kinaba: return ans; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: double area( const vector<CMP>& q ) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: double a = 0.0; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CMP o = q[0]; 4fd800b3a8 2011-02-23 kinaba: for(int i=1; i+1<q.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: a += outer_prod(q[i]-o, q[i+1]-o); 4fd800b3a8 2011-02-23 kinaba: return abs(a)/2; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: class BatmanAndRobin { public: 4fd800b3a8 2011-02-23 kinaba: double minArea(vector <int> x, vector <int> y) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: int N = x.size(); 4fd800b3a8 2011-02-23 kinaba: vector<CMP> p; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: p.push_back(CMP(x[i],y[i])); 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: const double eps = 1e-6; 4fd800b3a8 2011-02-23 kinaba: CMP diff[] = {CMP(eps,0), CMP(0,eps), CMP(-eps,0), CMP(0,-eps)}; 4fd800b3a8 2011-02-23 kinaba: double answer = area(convex_hull(p)); 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<N; ++i) 4fd800b3a8 2011-02-23 kinaba: for(int j=i+1; j<N; ++j) { 4fd800b3a8 2011-02-23 kinaba: for(int di=0; di<4; ++di) 4fd800b3a8 2011-02-23 kinaba: for(int dj=0; dj<4; ++dj) { 4fd800b3a8 2011-02-23 kinaba: vector<CMP> a = left_of(p, p[i]+diff[di], p[j]+diff[dj]); 4fd800b3a8 2011-02-23 kinaba: vector<CMP> b = right_of(p, p[i]+diff[di], p[j]+diff[dj]); 4fd800b3a8 2011-02-23 kinaba: double aa = a.size()<=2 ? 0 : area(convex_hull(a)); 4fd800b3a8 2011-02-23 kinaba: double bb = b.size()<=2 ? 0 : area(convex_hull(b)); 4fd800b3a8 2011-02-23 kinaba: answer = min(answer, max(aa,bb)); 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: return answer; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: vector<CMP> left_of(const vector<CMP>& p, const CMP& o, CMP v) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: v -= o; 4fd800b3a8 2011-02-23 kinaba: vector<CMP> r; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<p.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( is_left(p[i]-o, v) ) 4fd800b3a8 2011-02-23 kinaba: r.push_back(p[i]); 4fd800b3a8 2011-02-23 kinaba: return r; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: vector<CMP> right_of(const vector<CMP>& p, const CMP& o, CMP v) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: v -= o; 4fd800b3a8 2011-02-23 kinaba: vector<CMP> r; 4fd800b3a8 2011-02-23 kinaba: for(int i=0; i<p.size(); ++i) 4fd800b3a8 2011-02-23 kinaba: if( !is_left(p[i]-o, v) ) 4fd800b3a8 2011-02-23 kinaba: r.push_back(p[i]); 4fd800b3a8 2011-02-23 kinaba: return r; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: bool is_left(const CMP& p, const CMP& v) 4fd800b3a8 2011-02-23 kinaba: { 4fd800b3a8 2011-02-23 kinaba: return arg(p/v)>0; 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: }; 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: // BEGIN CUT HERE 4fd800b3a8 2011-02-23 kinaba: #include <ctime> 4fd800b3a8 2011-02-23 kinaba: double start_time; string timer() 4fd800b3a8 2011-02-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 4fd800b3a8 2011-02-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 4fd800b3a8 2011-02-23 kinaba: { os << "{ "; 4fd800b3a8 2011-02-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 4fd800b3a8 2011-02-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 4fd800b3a8 2011-02-23 kinaba: void verify_case(const double& Expected, const double& Received) { 4fd800b3a8 2011-02-23 kinaba: bool ok = (abs(Expected - Received) < 1e-9); 4fd800b3a8 2011-02-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 4fd800b3a8 2011-02-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 4fd800b3a8 2011-02-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 4fd800b3a8 2011-02-23 kinaba: #define END verify_case(_, BatmanAndRobin().minArea(x, y));} 4fd800b3a8 2011-02-23 kinaba: int main(){ 4fd800b3a8 2011-02-23 kinaba: 4fd800b3a8 2011-02-23 kinaba: CASE(0) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {100,100,90,90,-100,-100,-90,-90}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int y_[] = {100,90,100,90,-100,-90,-100,-90}; 4fd800b3a8 2011-02-23 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 100.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(1) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {-1000,-1000,1000,1000,1000,-1000}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int y_[] = {-1000,1000,-1000,1000,0,0}; 4fd800b3a8 2011-02-23 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 0.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(2) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {-1000,-1000,1000,1000,0}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int y_[] = {-1000,1000,-1000,1000,0}; 4fd800b3a8 2011-02-23 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 1000000.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(3) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {-904,-812,-763,-735,-692,-614,-602,-563,-435,-243,-87,-52,-28,121,126,149,157,185,315,336,390,470,528,591,673,798,815,837,853,874}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int y_[] = {786,10,-144,949,37,-857,-446,-969,-861,-712,5,-972,-3,-202,-845,559,-244,-542,-421,422,526,-501,-791,-899,-315,281,-275,467,743,-321}; 4fd800b3a8 2011-02-23 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 4fd800b3a8 2011-02-23 kinaba: double _ = 1067472.0; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: CASE(4) 4fd800b3a8 2011-02-23 kinaba: int x_[] = {-904,-812,-763,-735,-692,-614,-602,-563,-435,-243,-87,-52,-28,121,126,149,157,185,315,336,390,470,528,591,673,798,815,837,853,874,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int y_[] = {786,10,-144,949,37,-857,-446,-969,-861,-712,5,-972,-3,-202,-845,559,-244,-542,-421,422,526,-501,-791,-899,-315,281,-275,467,743,-321,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; 4fd800b3a8 2011-02-23 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 4fd800b3a8 2011-02-23 kinaba: double _ = -1; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: /* 4fd800b3a8 2011-02-23 kinaba: CASE(5) 4fd800b3a8 2011-02-23 kinaba: int x_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); 4fd800b3a8 2011-02-23 kinaba: int y_[] = ; 4fd800b3a8 2011-02-23 kinaba: vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); 4fd800b3a8 2011-02-23 kinaba: double _ = ; 4fd800b3a8 2011-02-23 kinaba: END 4fd800b3a8 2011-02-23 kinaba: */ 4fd800b3a8 2011-02-23 kinaba: } 4fd800b3a8 2011-02-23 kinaba: // END CUT HERE