D - 三角形の分類
問題概略
高々2000個の点が与えられる、3点を選んだ時、鈍角三角形、直角三角形、鋭角三角形の数を数えよ。
制約
任意の三点は同一直線上にない。
解法
ある点について、偏角でソートすればいい。
角度が2周するように配列を追加してやって、自分+180度以内について二分探索で見てやれば重複せずに数えられる。
public static void solve() throws Exception { //longを忘れるなオーバーフローするぞ N = ni(); x = niah(N, 2); y = niah(N, 2); long all = N * 1L * (N - 1) * (N - 2) / (3 * 2 * 1); long cnt90 = 0; long cnt = 0; for (int o = 0; o < N; o++) { ArrayList<Double> v = new ArrayList<>(); for (int i = 0; i < N; i++) { if (i == o) continue; v.add(atan2(y[i] - y[o], x[i] - x[o])); v.add(atan2(y[i] - y[o], x[i] - x[o]) + PI * 2); } Collections.sort(v); for (int i = 0; i < N - 1; i++) { double ang = v.get(i); cnt90 += upperBound(v, ang + PI / 2 + EPS) - lowerBound(v, ang + PI / 2 - EPS); cnt += lowerBound(v, ang + PI - EPS) - upperBound(v, ang + PI / 2 + EPS); } } long ei = all - cnt90 - cnt; System.out.println(ei + " " + cnt90 + " " + cnt); } || 参考