問題
平面上に個の点がある。半径の円内から無作為に1箇所選んだとき、番目の点が一番近くなる確率を求めよ。
解法
が十分大きいので、細かい部分は無視されて点に吸い込まれる角度だけが重要となる。個の点集合に関する凸包を求めて、その頂点となっている点について内角を求めればその頂点に入る角度がわかる。
制約が緩くまでは許されるためかなり手抜きの実装で良い。番目の点から見て、端として番目の点を固定して、番目の点を含めるのに時計回りで何度必要かというループを回すことで解ける。
反省
コンテスト時に解いた(および解説を読んだ)記憶がかなり残っていたので方針はすぐにわかったが、実装でかなり手間取った。で良いのでかなり綺麗に書けることに気が付いて、開始から30分ほどでようやく実装できたがWA。
どこが間違っているかわからなかったのでDropBoxに上げられているテストケースを見た。単に真下にある点に対する角度を間違ってとしていただけだった(が正しい)。最初は度数法で書いていたのを、acos
がラジアンで返すものだったので全てラジアンに修正した際に間違ってしまったのだった。基本的にラジアンで扱っていくのが良さそうか。
定数を利用するために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)); } }