読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

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

問題概要

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

解法

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

コード

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;
	}
};