#2351. 保镖

    ID: 2351 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest37来源:qoj.ac数据:公开样例计算几何数学

保镖

保镖

题目描述

3 保镖 3.1 题目描述 九条可怜是一个贪玩的女孩子。 一个可爱的女孩子出门在外和朋友玩,难免会遇到危险,于是可怜的爸爸悄悄的安插了n 位保镖在暗中保护她。因为可怜是一个要强的女孩子,所以她的爸爸不想让她知道她的身边有 这么多的保镖,因此保镖们必须通过定期的换岗来避免被可怜发现。 一次理想的换岗是:距离可怜远的保镖被换到了较近的位置,距离可怜近的保镖被换到了 较远的位置。经过一系列安排,保镖们会按照如下的方式进行换岗: • 换岗时,可怜和保镖们的位置可以被抽象成二维平面直角坐标系上的点。设可怜的位置为 O,保镖的位置为Pi,换岗后的位置为P ′ i • 在换岗前后,保镖和可怜的相对位置不变。即对于∀i ∈[1, n],P ′ i 在射线OPi 上。 • 在换岗前后,保镖和可怜的距离变成了原来的倒数。即对于∀i ∈[1, n],|OPi||OP ′ i| = 1。 同时,保镖的位置决定了可怜的安全度。如果在外围的保镖越多,那么他们能观察到的信 息就越多,可怜就越安全。因此,我们定义这些保镖的位置的凸包的顶点个数为可怜的安全度。 然而,可怜的行踪总是神出鬼没的。这一天,保镖们跟丢了可怜,只知道可怜下次会在以 (x1, y1) 为左下角,以(x2, y2) 为右上角的矩形区域内出现,具体的位置服从这个矩形区域内的 均匀分布(可以理解为等概率随机)。因为保镖们已经有很长时间没有换岗了,于是他们打算在 可怜下次出现的时候换岗。同时,在极小的概率下,可怜可能会出现在和某个保镖相同的位置 上。这时这个保镖会被发现,从而他会保持位置不动,而其他的保镖还是会按照上述规则进行 换岗。 现在,可怜的爸爸想要计算,保镖们在换岗后,可怜的安全度的期望是多少。 如果你对凸包不太熟悉,这儿给出凸包形式化的定义: • 对于一个简单多边形,它是凸多边形当且仅当它内部任意两点的连线在它的内部。 • 对于一个点集P,它的凸包为包含所有点面积最小的没有三个连续顶点共线的凸多边形。 3.2 输入格式 第一行输入一个整数n,表示保镖的数量。 第二行输入四个整数x1, y1, x2, y2,表示可怜可能出现的矩形区域。 接下来n 行每行两个整数a, b,表示一个保镖的坐标。保证保镖的坐标两两不同。 3.3 输出格式 输出一行一个实数表示凸包节点数的期望。 当你的答案与标准输出的绝对误差或相对误差在10−7 内时,就会被视为正确。 7

3.4 样例输入 4 0 0 1 1 0 0 2 0 0 1 1 1 3.5 样例输出 3.7853981633974474 3.6 样例解䞞 这儿画出可怜出现在(1, 0) 时的情况,如下图所示,1, 2, 4 号保镖的位置保持不变,分别为 P1, P2, P4,3 号保镖从P3 变到了P ′ 3,坐标为(1 2, 1 2)。 这时四个保镖的位置P1, P2, P ′ 3, P4 的凸包为三角形P1, P4, P2,因此可怜的安全度为3。注 意这时P ′ 3 正好落在边P1P4 上,但是根据凸包的定义,它不是顶点。 3.7 数据㣗围与约定 测试点 n 测试点 n 1 ≤3 6 ≤50 2 ≤4 7 ≤350 3 8 4 ≤50 9 ≤2000 5 10 对于100% 的数据,保证0 ≤a, b, x0, x1, y0, y1 ≤105, x0 < x1, y0 < y1, n ≥3。 对于100% 的数据,保证保镖的位置两两不同。 8

同时为了避免可能出现的㊒度误差,在所有实际的测试数据以及大样例中,保证可怜可能 出现的矩形区域的长宽都不小于103,即x1 −x0, y1 −y0 ≥103. 9

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
0 0 1 1
0 0
2 0
0 1
1 1
3.7853981633974474