TopCoder, Single Round Match 641, Division 2, Level 2 : TrianglesContainOriginEasy

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13547&rd=16084

問題概要

　平面上の点集合が与えられる．この点集合から 3 点を選んで，その 3 点を頂点とする三角形を作ることを考える．点 が三角形の内部に含まれるような 3 点の選び方の総数を求めよ．
　点集合の大きさは 50 を超えない．また．点集合に を加えたとき，集合中の任意の 3 点は同一直線上に並ばない．

解法

　点集合の大きさを と書きます．
　点集合から 3 点を選ぶ方法の総数は で，与えられた制約の上ではさほど大きな値になりません．従って，3 点の選び方を全て試して実際に三角形を作り， が三角形の内部に含まれるか否かを 1 つずつ判定して数え上げることができます．
　三角形を決めたとき，点がその内部に含まれるか否かを判定する方法について書いておきます．三角形の頂点を ，内外判定をしたい点を とします．このとき，3 つの外積 の z 軸方向に対応する要素の符号が等しければ，点 は三角形 の（strictly に）内部にあると言えます．この問題の場合は直線上に 3 点以上並ばないので，点が三角形の辺上に乗る場合などは考える必要はありません．（以下のコードでは手持ちのライブラリからコピペした内外判定を使っているので辺上の判定が入っています）

コード

template < typename T = int > using VT = vector<T>; template < typename T = int > using VVT = VT< VT<T> >;

#define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define EB emplace_back

#include <complex>
using Point =  complex< double >;
constexpr double EPS = 1e-8;
constexpr double PI = acos( -1 );

// 内積（ドット積）
double dot( const Point &a, const Point &b )
{
	return a.real() * b.real() + a.imag() * b.imag();
}

// 外積（クロス積）
double cross( const Point &a, const Point &b )
{
	return a.real() * b.imag() - a.imag() * b.real();
}

// 点 p が線分 ( q1, q2 ) に乗っているか
// include : dot, cross
bool intersectPS( const Point &p, const Point &q1, const Point &q2 )
{
	// 端点からの p へのベクトルの外積が 0 ⇔ 端点からのベクトルが並行 ⇔ 直線 ( q1, q2 ) に点 p が乗る
	// p から端点へのベクトルの内積が 0 以下 ⇔ 点 p が q1, q2 の内側にある
	return abs( cross( q1 - p, q2 - p ) ) <= EPS && dot( q1 - p, q2 - p ) <= EPS;
}

// 三角形 ( a, b, c ) の中に点 p があるか
// include : cross, intersectPS
bool point_in_triangle( const Point &a, const Point &b, const Point &c, const Point &p )
{
	int res = 0;
	res += EPS < cross( b - a, p - a ) ? 1 : -1;
	res += EPS < cross( c - b, p - b ) ? 1 : -1;
	res += EPS < cross( a - c, p - c ) ? 1 : -1;

	if ( abs( res ) == 3 ) // 外積の符号が一致すると真
	{
		return true;
	}
	// いずれかの辺に乗るか
	return intersectPS( p, a, b ) || intersectPS( p, b, c ) || intersectPS( p, c, a );
}

constexpr Point O( 0, 0 );

class TrianglesContainOriginEasy
{
public:
	int count( vector <int> x, vector <int> y )
	{
		const int N = x.size();

		VT< Point > ps;
		REP( i, 0, N )
		{
			ps.EB( x[i], y[i] );
		}


		int res = 0;
		REP( i, 0, N )
		{
			REP( j, 0, i )
			{
				REP( k, 0, j )
				{
					res += point_in_triangle( ps[i], ps[j], ps[k], O );
				}
			}
		}

		return res;
	}
};