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