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