九条可怜是一个贪玩的女孩子。

一个可爱的女孩子出门在外和朋友玩，难免会遇到危险，于是可怜的爸爸悄悄的安插了 $n$ 位保镖在暗中保护她。因为可怜是一个要强的女孩子，所以她的爸爸不想让她知道她的身边有这么多的保镖，因此保镖们必须通过定期的换岗来避免被可怜发现。

一次理想的换岗是：距离可怜远的保镖被换到了较近的位置，距离可怜近的保镖被换到了较远的位置。经过一系列安排，保镖们会按照如下的方式进行换岗：

• 换岗时，可怜和保镖们的位置可以被抽象成二维平面直角坐标系上的点。设可怜的位置为 $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$，它的凸包为包含所有点面积最小的没有三个连续顶点共线的凸多边形。

输入格式

第一行输入一个整数 $n$， 表示保镖的数量。

第二行输入四个整数 $x_1,y_1,x_2,y_2$， 表示可怜可能出现的矩形区域。

接下来 $n$ 行每行两个整数 $a,b$，表示一个保镖的坐标。保证保镖的坐标两两不同。

输出格式

输出一行一个实数表示凸包节点数的期望。

当你的答案与标准输出的绝对误差或相对误差在 $10^{-7}$ 内时，就会被视为正确。

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

3.7853981633974474

这儿画出可怜出现在 $(1,0)$ 时的情况，如下图所示，$1,2,4$ 号保镖的位置保持不变，分别为 $P_1,P_2,P_4$，$3$ 号保镖从 $P_3$ 变到了 $P'_3$，坐标为 $(\frac{1}{2},\frac{1}{2})$。

这时四个保镖的位置 $P_1,P_2,P'_3,P_4$ 的凸包为三角形 $P_1,P_4,P_2$，因此可怜的安全度为 $3$。注意这时 $P'_3$ 正好落在边 $P_1P_4$ 上，但是根据凸包的定义，它不是顶点。

限制与约定

对于 $100 \%$ 的数据，保证 $0 \leq a,b,x_0,x_1,y_0,y_1 \leq 10^5, x_0 < x_1, y_0 < y_1, n \geq 3$。

对于 $100 \%$ 的数据，保证保镖的位置两两不同。

同时为了避免可能出现的精度误差，在所有实际的测试数据以及大样例中，保证可怜可能出现的矩形区域的长宽都不小于 $10^3$，即 $x_1-x_0,y_1-y_0 \geq 10^3$.

时间限制: 4s

空间限制: 512MB

下载

样例数据下载