4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: // Area of a polygon
4fd800b3a8 2011-02-23        kinaba: //   O(N)
4fd800b3a8 2011-02-23        kinaba: //
4fd800b3a8 2011-02-23        kinaba: // Verified by
4fd800b3a8 2011-02-23        kinaba: //   - SRM 337 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //   - SRM 486 Div1 LV3
4fd800b3a8 2011-02-23        kinaba: //-------------------------------------------------------------
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: double outer_prod( pt a, pt b )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	return (a.real()*b.imag() - b.real()*a.imag())/2;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: double area( const vector<pt>& 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: 	pt 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: }