バイトの競プロメモ

主に競技プログラミング

B - Holes AtCoder Grand Contest 021

問題概略
N個の点がある。R = 10^10^10^10として、半径R内の円無いから無作為に一点を選ぶ際、それぞれの点が一番近い確率を求めよ。

制約
2≤N≤100

xi , yi ≤106(1≤i≤N)

与えられる点は全て相異なる

解法
それぞれの点が一番近い範囲を書いてみると、凸包上で真ん中を二分するいくつかの線で表されることがわかる。
今Rがとても大きいので、点付近は無視でき、線の角度が確率の大きさと一致する。

iからのベクトルを偏角でソートして、角度が最も大きい隣合う2つのベクトルが凸包上の2点を指す。
隣り合う者同士で見ていくと、180 -> -180の空間が破れている場所は一箇所なのでそこは別視する

public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int[] x = niah(N, 2);
        int[] y = niah(N, 2);
        for (int i = 0; i < N; i++) {
            ArrayList<Double> ang = new ArrayList<>();
            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                ang.add(atan2(y[j] - y[i], x[j] - x[i]));
            }
            sort(ang);
            double max = 0;
            for (int j = 0; j < N - 2; j++) {
                max = Math.max(max, ang.get(j + 1) - ang.get(j));
            }
            max = Math.max(max, ang.get(0) - ang.get(N - 2) + 2 * PI);
            System.out.println(max < PI ? 0 : (max - PI) / 2 / PI);
        }
    }