TopCoder, Single Round Match 641, Division 1, Level 1 : TrianglesContainOrigin

問題文

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

問題概要

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

解法

　点集合の大きさを と書きます．
　制約以外は Division 2, Level 2 と同一ですが，こちらの問題では の時間をかけると TLE してしまいます．
　三角形を構成する点のうち，2 つが決まったとき，もう 1 つの点は，2 つの点に対し の「反対側」になければいけない，ということが予想できます．この「反対側」をきちんと定義するため，点の偏角に着目します．
　三角形を構成する二つの点の偏角が であったとき，三角形を構成するもう 1 つの点の偏角 は， の反対側より大きく， の反対側より小さくなければなりません．すなわち， を満たさなければなりません．
　偏角を予め昇順に列挙しておけば， を固定したときに条件式を満たす区間を二分探索により 時間で求めることができます．この場合，全体のオーダーは となります．
　ところで， を昇順に試していくとすれば，式中の も単調増加します．つまり，区間の端点は常に後ろ方向に動くので，直前の に対する区間の端点を覚えておいて，単純な while ループで更新するという処理を考えることができます． が昇順に動く間，この while ループによって区間の始点が更新される回数は 回です． についても同様のことが言えて， を全探索する間に区間の終点が更新される回数は となります．従って， 時間で問題を解くことができます．

コード

using LL = long long; using ULL = unsigned long long;
using PII = pair< int, int >; using VPII = vector< PII >;
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 ALL( c ) ( c ).begin(), ( c ).end()

constexpr double PI = acos( -1 );

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

		VT< double > angles;
		transform( ALL( x ), y.begin(), back_inserter( angles ), []( const int a, const int b ){ return atan2( b, a ); } );
		sort( ALL( angles ) );

		LL res = 0;
		int mi = 0, ma = 0;
		REP( i, 0, N )
		{
			while ( mi < N && angles[ mi ] < angles[i] + PI )
			{
				++mi;
			}

			ma = 0;
			REP( j, i + 1, N )
			{
				if ( angles[i] + PI < angles[j] )
				{
					break;
				}

				while ( ma < N && angles[ ma ] < angles[j] + PI )
				{
					++ma;
				}

				res += ma - mi;
			}
		}
		return res;
	}
};