TopCoder SRM 641 Div1 Easy: TrianglesContainOrigin (幾何)

解法

kmjp.hatenablog.jp

各点の仰角を求めてargsに入れておく。0以下になる場合には2*PIを足しておく。atan2を使うと仰角を簡単に求めることが出来る。argsをソートし、args[i]+PI

コード

import java.util.ArrayList;
import java.util.Collections;

public class TrianglesContainOrigin {

	public long count(int[] x, int[] y) {
		int N = x.length;
		ArrayList<Double> args = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			double arg = Math.atan2(y[i], x[i]);
			if (arg < 0) {
				arg += 2 * Math.PI;
			}
			args.add(arg);
		}
		Collections.sort(args);

		long cnt = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (args.get(j) < args.get(i) + Math.PI) {
					// args[i]<args[j]<args[i]+PI
					// args[i]+PI<k<args[j]+PIとなるkをさがす
					int p = ~Collections.binarySearch(args, args.get(i) + Math.PI);
					int q = ~Collections.binarySearch(args, args.get(j) + Math.PI);
					cnt += q - p;
				}
			}
		}

		return cnt;
	}

}