はまやんはまやんはまやん

hamayanhamayan's blog

Holes [AtCoder Grand Contest 021 B]

https://agc021.contest.atcoder.jp/tasks/agc021_b

前提知識

  • 幾何の知識(凸包と外角)

解法

https://agc021.contest.atcoder.jp/submissions/2134465

解法がまったくもって思いつかなかった。
satanicさんの思考過程が参考になる
 
つまり、凸包を取って凸包の頂点の外角/2Piが答えになる。
幾何ライブラリなので、Spaghetti Sourceから取ってきて貼っただけ。
あとは、隣接する3頂点について角度を求めると答え。
(これもよく分からなくてphylloさんのやつを流用した)

int N;
P po[101];
double ans[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
 
    vector<P> v;
    rep(i, 0, N) {
        double x, y; cin >> x >> y;
        po[i] = P(x, y);
        v.push_back(po[i]);
    }
 
    if (N == 2) {
        printf("0.5\n0.5\n");
        return;
    }
 
    auto ch = convex_hull(v);
    int n = ch.size();
    rep(i, 0, n) {
        int a = i;
        int b = (i + 1) % n;
        int c = (i + 2) % n;
 
        int id = -1;
        rep(j, 0, N) if (abs(po[j] - ch[b]) < EPS) id = j;
        ans[id] = threePointArgument(ch[a], ch[b], ch[c]) / (2.0 * PI);
    }
 
    rep(i, 0, N) printf("%.10f\n", ans[i]);
}