AGC021 - B - Holes - tinumu's reminder

問題文

atcoder.jp
十分大きい円(半径 $R = 10^{10^{10^{10}}}$ )の中に穴が $N$ 個あって、穴 $1$ , 穴 $2$ , $\cdots$ 穴 $N$ まである。
確率的に一様にどこかの座標にすぬけ君を置く。
その時すぬけ君はユークリッド距離で一番近い穴に入る。
このとき、全ての $i$ において穴 $i$ に入る確率を求めよ

解法

f:id:tinumukiti631:20200327164420j:plain

まず $2$ 点について考えると、垂直二等分線を引けば、近い側が明らかになる。
$R$ が十分大きいので、は原点に垂直二等分線を引いたのと近似できる。
そのため、答えはどちらも $0.5$ になる。

次に、いくつかの穴があった時のある穴のある点 $P$ について着目してみる。
f:id:tinumukiti631:20200327164426j:plain
他の穴の側に行かなければいいので、他の穴についての垂直二等分線を見て、 $P$ 側である方の範囲を AND すれば(積集合を求めれば？)、範囲が分かることになる。

もし、点 $P$ を完全に囲うような形で、垂直二等分線を引かれていた場合、その面積は $R$ に依存しない定数になるため、 $R$ が十分大きいので答えが $0$ になる。
このような条件は点 $P$ がこの点集合の凸包に含まれていないことが同値である。

凸包に含まれていない点の答えが $0$ になるとわかった。
では、凸包に含まれている点はどうなっているだろうか。
さっきと同じ理論で、垂直二等分線を任意の位置に移動しても答えがほとんど変わらないので全て点 $P$ に移動するものと考えてみる。
すると、実は関係しているものは凸包において点 $P$ に隣り合っている点に対する線のみであるということが分かる。

凸包において隣り合っている点をそれぞれ点 $A, B$ と置いてみる。
$\angle APB = \theta$ と置いてみると、
求めたい角度は $\pi - \theta$ であることが分かる。(凸性があるので $\theta < \pi$ である、よって $\pi - \theta > 0$ )。
答えは確率であるため、答えは $\displaystyle \frac{\pi - \theta}{2 \pi}$ となる。

$\theta$ の見つけ方は色々とあると思う。
今回の問題では実は凸包の専門的なアルゴリズム(Andrew Scanみたいな)を使わなくても解けて、
点 $P$ からの任意の点の角度をソートした時に差が $\pi$ を超えた点 $A, B$ があるなら、 $P$ は凸包の点で $A, B$ は $P$ と隣り合っている。
$\angle APB$ の中に全部角度が収まっていることになるからである。
そしてその角度は $\pi$ より小さいので $P$ は凸包の点である。

Source

V2は $2$ 次元ベクトルのデータ構造です

void Main() {
	int N; cin >> N;
	vector<V2> points(N);
	for (auto &p : points) cin >> p.x >> p.y;
	vdouble ans(N, 0);
	for (int i = 0; i < N; i++) {
		vdouble angles;
		for (int j = 0; j < N; j++) {
			if (i==j) continue;
			V2 vec = points[j]-points[i];
			angles.push_back(atan2(vec.y, vec.x));
		}
		sort(begin(angles), end(angles));
		angles.push_back(angles[0]+2*M_PI);
		for (int j = 0; j < angles.size(); j++) {
			int k = j+1;
			if (k >= angles.size()) k -= angles.size();
			if (angles[k]-angles[j] > M_PI + EPS) {
				ans[i] = angles[k]-angles[j]-M_PI;
			}
		}
		cout << ans[i] / 2 / M_PI << el;
	}
}

感想

近似できるの、面白いし角度とかの性質とか知れたので面白かった。