バイトの競プロメモ

主に競技プログラミング

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





参考