序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
---|
九条可怜是一个贪玩的女孩子。
一个可爱的女孩子出门在外和朋友玩,难免会遇到危险,于是可怜的爸爸悄悄的安插了 nn 位保镖在暗中保护她。因为可怜是一个要强的女孩子,所以她的爸爸不想让她知道她的身边有这么多的保镖,因此保镖们必须通过定期的换岗来避免被可怜发现。
一次理想的换岗是:距离可怜远的保镖被换到了较近的位置,距离可怜近的保镖被换到了较远的位置。经过一系列安排,保镖们会按照如下的方式进行换岗:
- 换岗时,可怜和保镖们的位置可以被抽象成二维平面直角坐标系上的点。设可怜的位置为 $O$,保镖的位置为 $P_i$ ,换岗后的位置为 $P'_i$
- 在换岗前后,保镖和可怜的相对位置不变。即对于 $\forall i \in [1,n] ,P'_i$ 在射线 $OP_i$ 上。
- 在换岗前后,保镖和可怜的距离变成了原来的倒数。即对于 $ \forall i \in [1,n],|OP_i||OP'_i|=1$。
同时,保镖的位置决定了可怜的安全度。如果在外围的保镖越多,那么他们能观察到的信息就越多,可怜就越安全。因此,我们定义这些保镖的位置的凸包的顶点个数为可怜的安全度。
然而,可怜的行踪总是神出鬼没的。这一天,保镖们跟丢了可怜,只知道可怜下次会在以 $(x_1,y_1)$ 为左下角,以 $ (x_2,y_2)$ 为右上角的矩形区域内出现,具体的位置服从这个矩形区域内的均匀分布(可以理解为等概率随机)。因为保镖们已经有很长时间没有换岗了,于是他们打算在可怜下次出现的时候换岗。同时,在极小的概率下,可怜可能会出现在和某个保镖相同的位置上。这时这个保镖会被发现,从而他会保持位置不动,而其他的保镖还是会按照上述规则进行换岗。
现在,可怜的爸爸想要计算,保镖们在换岗后,可怜的安全度的期望是多少。
如果你对凸包不太熟悉,这儿给出凸包形式化的定义:
- 对于一个简单多边形,它是凸多边形当且仅当它内部任意两点的连线在它的内部。
- 对于一个点集 $P$,它的凸包为包含所有点面积最小的没有三个连续顶点共线的凸多边形。