TopCoder SRM 641 Div1 Easy TrianglesContainOrigin、Div2 Medium TrianglesContainOriginEasy

SRM641に参加。
Easyをそこそこの時間で解き、1Challengeでレート微増。
http://community.topcoder.com/stat?c=problem_statement&pm=13309
http://community.topcoder.com/stat?c=problem_statement&pm=13547

問題

２次元座標上でN個の点の位置が与えられる。
このうち３つの点の組のうち、３点を頂点とする三角形が原点を含むものの数を求めよ。

なお、３点が同一線上にあったり、２点の同一線上に原点が来ることはない。

解法

Div2 MediumはN<=50のため、３点総当たりで全パターンの三角形を試せばよい。
Div1 EasyはN<=250のためO(N^3)では間に合わない。

そこでまず全部の点を偏角の順にソートする。
そして２点i,jを総当たりし、３点目として取れる点の数を列挙すればよい。
先に決めた２点の偏角をarg(i)、arg(j)とすると、３点目kの偏角がarg(i)+π＜arg(k)＜arg(j)+πとなるkの数を求めればよい。

条件を満たすkの数は、偏角順にソートした点に対しlower_bound等で求めればO(N^2*logN)だし、尺取法ならO(N^2)で求めることができる。
以下の解法は前者。

class TrianglesContainOrigin {
	public:
	int N;
	long long count(vector <int> x, vector <int> y) {
		int i,j;
		ll ret=0;
		double pi=atan(1)*4;
		N=x.size();
		vector<double> V;
		FOR(i,N) {
			double d=atan2(y[i],x[i]);
			if(d<0) d+=2*pi;
			V.push_back(d);
		}
		sort(V.begin(),V.end());
		FOR(i,N) for(j=i+1;j<N;j++) {
			if(V[j]<V[i]+pi) {
				int x2=lower_bound(V.begin(),V.end(),V[i]+pi)-V.begin();
				int y2=lower_bound(V.begin(),V.end(),V[j]+pi)-V.begin();
				ret+=y2-x2;
			}
		}
		
		return ret;
	}
}
||

*まとめ