23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: // Area of a polygon
23dfcca431 2011-02-23        kinaba: //   O(N)
23dfcca431 2011-02-23        kinaba: //
23dfcca431 2011-02-23        kinaba: // Verified by
23dfcca431 2011-02-23        kinaba: //   - SRM 337 Div1 LV3
23dfcca431 2011-02-23        kinaba: //   - SRM 486 Div1 LV3
23dfcca431 2011-02-23        kinaba: //-------------------------------------------------------------
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: double outer_prod( pt a, pt b )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	return (a.real()*b.imag() - b.real()*a.imag())/2;
23dfcca431 2011-02-23        kinaba: }
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: double area( const vector<pt>& q )
23dfcca431 2011-02-23        kinaba: {
23dfcca431 2011-02-23        kinaba: 	double a = 0.0;
23dfcca431 2011-02-23        kinaba: 
23dfcca431 2011-02-23        kinaba: 	pt o = q[0];
23dfcca431 2011-02-23        kinaba: 	for(int i=1; i+1<q.size(); ++i)
23dfcca431 2011-02-23        kinaba: 		a += outer_prod(q[i]-o, q[i+1]-o);
23dfcca431 2011-02-23        kinaba: 	return abs(a) / 2;
23dfcca431 2011-02-23        kinaba: }