AtCoder Grand Contest 021 B - Holes

問題

 平面上にN個の点がある。半径 R = 10^{10^{10^{10}}}の円内から無作為に1箇所選んだとき、i番目の点が一番近くなる確率を求めよ。

解法

 Rが十分大きいので、細かい部分は無視されて点に吸い込まれる角度だけが重要となる。N個の点集合に関する凸包を求めて、その頂点となっている点について内角を求めればその頂点に入る角度がわかる。 f:id:tokumini:20180802111853p:plain

 制約が緩くO(N^{3})までは許されるためかなり手抜きの実装で良い。i番目の点から見て、端としてj番目の点を固定して、k番目の点を含めるのに時計回りで何度必要かというループを回すことで解ける。

f:id:tokumini:20180802111912p:plain

反省

 コンテスト時に解いた(および解説を読んだ)記憶がかなり残っていたので方針はすぐにわかったが、実装でかなり手間取った。O(N^{3})で良いのでかなり綺麗に書けることに気が付いて、開始から30分ほどでようやく実装できたがWA。

 どこが間違っているかわからなかったのでDropBoxに上げられているテストケースを見た。単に真下にある点に対する角度を間違って2\piとしていただけだった(\piが正しい)。最初は度数法で書いていたのを、acosラジアンで返すものだったので全てラジアンに修正した際に間違ってしまったのだった。基本的にラジアンで扱っていくのが良さそうか。

 定数\piを利用するためにconst double PI = acos(-1);ということをしたが、#define _USE_MATH_DEFINESを定義してからcmathを読み込めばM_PIという定義済みマクロが使えるようだ。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
    const double PI = acos(-1);

    ll N;
    cin >> N;
    vector<double> x(N), y(N);
    for (ll i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }

    //iからjへの角度を求める
    //真上が0度で時計回りに計測
    //iから見てi以外の点が全てある180度の中に収まっていたら凸包の頂点になる
    vector<vector<double>> angle(N, vector<double>(N));

    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }

            if (x[j] == x[i]) {
                if (y[j] > y[i]) {
                    angle[i][j] = 0.0;
                } else {
                    angle[i][j] = PI;
                }
            } else if (x[j] > x[i]) {
                double diff_x = x[j] - x[i];
                double diff_y = y[j] - y[i];
                angle[i][j] = acos(diff_y / sqrt(pow(diff_x, 2) + pow(diff_y, 2)));
            } else {
                double diff_x = x[j] - x[i];
                double diff_y = y[j] - y[i];
                double a = acos(diff_y / sqrt(pow(diff_x, 2) + pow(diff_y, 2)));
                angle[i][j] = 2.0 * PI - a;
            }
        }
    }

    vector<double> min_angles(N);
    for (ll i = 0; i < N; i++) {
        double min_angle = INT_MAX;
        for (ll j = 0; j < N; j++) {
            if (j == i) {
                continue;
            }
            //iから見て、jを一番端としてここから全部の点を含めるのに時計回りで何度必要かを計算
            double tmp = 0;
            for (ll k = 0; k < N; k++) {
                if (k == i || k == j) {
                    continue;
                }
                if (angle[i][k] < angle[i][j]) {
                    tmp = max(tmp, angle[i][k] + 2.0 * PI - angle[i][j]);
                } else {
                    tmp = max(tmp, angle[i][k] - angle[i][j]);
                }
            }
            min_angle = min(min_angle, tmp);
        }

        min_angles[i] = min_angle;
    }

    for (ll i = 0; i < N; i++) {
        printf("%.10f\n", max(PI - min_angles[i], 0.0) / (2.0 * PI));
    }
}