2019-10-28 10:44 已编辑中山大学 C++

关注

2019 牛客多校 1F （详细证明）

https://ac.nowcoder.com/acm/contest/881/F

题目

Bobo has a triangle ABC with A(x1,y1),B(x2,y2)A(x1,y1),B(x2,y2) and C(x3,y3)C(x3,y3). Picking a point P uniformly in triangle ABC, he wants to know the expectation value $E=\max \{S_{PAB},S_{PBC},S_{PCA} \}$ , where $S_{XYZ}$ denotes the area of triangle XYZ.

Print the value of $36×E$ . It can be proved that it is always an integer.

解答

期望值是三角形面积的11/18, 下面给出证明。

已知A,B,C三点，P是三角形ABC内等概率分布的一个点，则可将P表示成：

$P = (1 - \sqrt{r_1}) A + (\sqrt{r_1} (1 - r_2)) B + (r_2 \sqrt{r_1}) C$

其中 $r_1, r_2 \sim U[0, 1]$

即 $r_1$ 和 $r_2$ 是两个独立的随机变量，在[0,1]内等概率分布。

uniform-random-point-in-triangle

不失一般性，设点A坐标为(0,0), $\overrightarrow{AB} = \overrightarrow{b}$ , $\overrightarrow{AC} = \overrightarrow{c}$

则有，

$\begin{aligned} S_{PAB} &= \frac{1}{2}\overrightarrow{AB}×\overrightarrow{AP} \\ &=\frac{1}{2} \overrightarrow{b}× (\sqrt{r_1} (1 - r_2) \overrightarrow{b} + r_2 \sqrt{r_1} \overrightarrow{c}) \\ &= \frac{1}{2} r_2 \sqrt{r_1} (\overrightarrow{b}× \overrightarrow{c}) \end{aligned} \\ \begin{aligned} S_{PBC} &= \frac{1}{2}\overrightarrow{BC}×\overrightarrow{BP} \\ &= \frac{1}{2} (\overrightarrow{c}-\overrightarrow{b})× (\sqrt{r_1} - r_2\sqrt{r_1}-1) \overrightarrow{b} + r_2 \sqrt{r_1} \overrightarrow{c}) \\ &= \frac{1}{2} (-\sqrt{r_1}+1)(\overrightarrow{b}× \overrightarrow{c}) \end{aligned} \\ \begin{aligned} S_{PAC} &= \frac{ 1}{2}\overrightarrow{CA}×\overrightarrow{CP} \\ &= \frac{1}{2} (-\overrightarrow{c})× (\sqrt{r_1} (1 - r_2) \overrightarrow{b} + (r_2 \sqrt{r_1}-1) \overrightarrow{c}) \\ &= \frac{1}{2} \sqrt{r_1} (1 - r_2) (\overrightarrow{b}× \overrightarrow{c}) \end{aligned} \\ \because S_{ABC} = \frac{1}{2} \overrightarrow{b}× \overrightarrow{c} \\ \therefore \max \{S_{PAB},S_{PBC},S_{PCA} \} = \max \{r_2 \sqrt{r_1},-\sqrt{r_1}+1,\sqrt{r_1} (1 - r_2) \} \cdot S_{ABC}$

下面证明 $E(\max \{r_2 \sqrt{r_1},-\sqrt{r_1}+1,\sqrt{r_1} (1 - r_2) \}) = \frac{11}{18}$

求概率密度函数

设随机变量 $X=\max \{r_2 \sqrt{r_1},-\sqrt{r_1}+1,\sqrt{r_1} (1 - r_2) \}$
则累积分布函数CDF可表示成 $P(X\leq t)=P((r_2 \sqrt{r_1} \leq t) \wedge ( -\sqrt{r_1}+1\leq t ) \wedge (\sqrt{r_1} (1 - r_2) \leq t ))$

表示成重积分，则有

$P(X\leq t) = \iint_{D}{\rm d}r_1{\rm d}r_2$

其中 $D=\left\{\begin{matrix}r_2 \sqrt{r_1} \leq t \\ -\sqrt{r_1}+1 \leq t \\ \sqrt{r_1} (1 - r_2) \leq t \\ 0 \leq r_1 \leq 1 \\ 0 \leq r_2 \leq 1 \end{matrix}\right.$

作变量代换， $\left\{\begin{aligned}u&=r_2\sqrt {r_1} \\ v &= \sqrt {r_1} \end{aligned}\right.$

反变换为, $\left\{\begin{aligned}r_1&=v^2 \\ r_2&=\frac{u}{v} \end{aligned}\right.$

雅克比行列式

$J=\begin{vmatrix} \frac{\partial r_1}{\partial u}& \frac{\partial r_1}{\partial v}\\ \frac{\partial r_2}{\partial u}& \frac{\partial r_2}{\partial v} \end{vmatrix}= \begin{vmatrix} 0 & 2v\\ \frac{1}{v}& -\frac{u}{v^2} \end{vmatrix} = -2$

(雅克比行列式居然如此简单)

$\therefore P(X\leq t) = \iint_{D}{\rm d}r_1{\rm d}r_2 = \iint_{D'}|-2|{\rm d}u{\rm d}v$

其中 $D'=\left\{\begin{matrix}u \leq t \\ v\geq 1-t \\ v \leq u+t \\ 0 \leq v \leq 1 \\ 0 \leq u \leq 1 \\ u \leq v \end{matrix}\right.$

最后一个限制由 $0 \leq \frac{u}{v}=r_2 \leq 1$ 得到。

$D'$ 区域如下图所示，分两种情况 $\frac{1}{3}\leq t\leq\frac{1}{2}$ 和 $\frac{1}{2} \leq t \leq 1$

(1/3这个下界是显然的)
积分区域D'

于是问题就变成了求阴影部分面积。

易得左图三角形面积的两倍是 $(3t-1)^2$ ，右边多边形面积两倍是 $-3t^2+6t-2$

$\therefore P(X\leq t) = \left\{\begin{matrix} (3t-1)^2 &, \frac{1}{3}\leq t\leq\frac{1}{2}\\ -3t^2+6t-2 & ,\frac{1}{2} \leq t \leq 1 \end{matrix}\right.$

由cdf求pdf，概率密度函数，得

$p(x) = \left\{\begin{matrix} 18x-6 &, \frac{1}{3}\leq t\leq\frac{1}{2}\\ -6x+6 & ,\frac{1}{2} \leq t \leq 1 \end{matrix}\right. \\ \therefore E(X) = \int_{\frac{1}{3}}^{\frac{1}{2}}(18x^2-6x){\rm d}x + \int_{\frac{1}{2}}^{1}(-6x^2+6x){\rm d}x = \frac{11}{18}$

证毕。