TopCoder SRM 641 Div1 Easy: TrianglesContainOrigin (幾何)
解法
各点の仰角を求めて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; } }