ぽえの競プロノート

最終更新: 2026-05-14 問題へのリンク 問題概要 正方形内部に $N$ 個のランダムな点を置き、それらすべてを線分で結んだとき、正方形が分割された領域の個数の期待値を求めよ。 ・$N \le 10^9$ ★3.5 解説 $4 \le N$ の時、 $N$ 個の点と線分の交点の個数を合わせて $V$ とする。$V$ 個の点から $2$ つの点を選び出す方法であって、その二点を通る線が存在するものの数を $E$ とする。また、この線は $2$ 点の間にほかの点が存在し得ない（確率が $0$ ）ので、頂点数 $V$ 辺数 $E$ の平面グラフとなる。すなわち、面の個数はオイラーの定理より $E-V+2$ である。 また、はじめに結んだ $\dbinom{N}{2}$ 個の線分同士の交点の個数を $X$ とすると、 $V=N+X$ 、 $E=\dbinom{N}{2} + 2X$ が成り立つことが分かるので、求める答えは  $\mathbb{E}\left[\dbinom{N}{2} - N + 2 + X\right] = \dbinom{N}{2} - N + 2 + \mathbb{E}[X]$ であることが分かる。 $N$ 個の点から $4$ 点を取り出すことを考えると、その $4$ 点をそれぞれ線分で結んだ時、交点が $0$ 個または $1$ 個できる。 交点ができる配置(左)とできない配置(右) 交点ができる確率を $P$ とすると、　$\mathbb{E}[X] = \dbinom{N}{4}P$ が得られる。サンプル 1 より、 $P = \dfrac{25}{36}$ が得られるので、答えは $\dbinom{N}{2} - N + 2 + \dbinom{N}{4} \cdot \dfrac{25}{36}$ である。 ただ、これだと面白くないので別の方法で $P=\dfrac{25}{36}$ を示す。 面積が $1$ である正方形の内部でランダムに選んだ $3$ 点がなす三角形の面積を $S$ とする。 $4$ 点のうちから $1$ 点を選び、他の $3$ 点がなす三角形の内部にある確率を考えると、 $P = 1 - 4 \cdot \mathbb{E}[S]$ が分かる。...