CF771F.Bear and Isomorphic Points

Bearland is a big square on the plane. It contains all points with coordinates not exceeding 106 by the absolute value.

There are n houses in Bearland. The i-th of them is located at the point (x__i, y__i). The n points are distinct, but some subsets of them may be collinear.

Bear Limak lives in the first house. He wants to destroy his house and build a new one somewhere in Bearland.

Bears don't like big changes. For every three points (houses) p__i, p__j and p__k, the sign of their cross product (p__j - p__i) × (p__k - p__i) should be the same before and after the relocation. If it was negative/positive/zero, it should still be negative/positive/zero respectively. This condition should be satisfied for all triples of indices (i, j, k), possibly equal to each other or different than 1. Additionally, Limak isn't allowed to build the house at the point where some other house already exists (but it can be the point where his old house was).

In the formula above, we define the difference and the cross product of points (a__x, a__y) and (b__x, b__y) as:

(a__x, a__y) - (b__x, b__y) = (a__x - b__x, a__y - b__y),

(a__x, a__y) × (b__x, b__y) = a__x·b__y - a__y·b__x.

Consider a set of possible new placements of Limak's house. Your task is to find the area of that set of points.

Formally, let's say that Limak chooses the new placement randomly (each coordinate is chosen independently uniformly at random from the interval [ - 106, 106]). Let p denote the probability of getting the allowed placement of new house. Let S denote the area of Bearland (S = 4·1012). Your task is to find p·S.

Bearland 是平面上的一个大正方形区域，包含所有坐标绝对值不超过 $10^6$ 的点。

Bearland 中有 $n$ 座房屋。第 $i$ 座房屋位于点 $(x_i,\,y_i)$。这 $n$ 个点互不相同，但其中某些子集可能共线。

Bear Limak 住在第一座房屋中。他想拆除自己的旧屋，并在 Bearland 内的某处新建一座房屋。

熊类不喜欢剧烈变动。对于任意三个点（房屋）$p_i$、$p_j$ 和 $p_k$，其叉积 $(p_j - p_i) \times (p_k - p_i)$ 的符号在搬迁前后必须保持一致：若原先为负/正/零，则搬迁后仍须为负/正/零。该条件需对所有三元组下标 $(i,\,j,\,k)$ 成立（下标可相等，也可不同于 $1$）。此外，Limak 不允许将新屋建在已有其他房屋的位置上（但可以建在他原来房屋所在的位置）。

在上述公式中，我们定义点 $(a_x,\,a_y)$ 与 $(b_x,\,b_y)$ 的差与叉积如下：

$$(a_x,\,a_y) - (b_x,\,b_y) = (a_x - b_x,\,a_y - b_y),$$

$$(a_x,\,a_y) \times (b_x,\,b_y) = a_x \cdot b_y - a_y \cdot b_x.$$

考虑 Limak 新建房屋所有可能位置所构成的集合。你的任务是求出该点集的面积。

形式化地，假设 Limak 随机选择新屋位置（每个坐标独立且均匀地从区间 $[-10^6,\,10^6]$ 中选取）。令 $p$ 表示选到合法位置的概率，令 $S$ 表示 Bearland 的面积（即 $S = 4 \cdot 10^{12}$）。你的任务是计算 $p \cdot S$。

The first line of the input contains an integer T (1 ≤ T ≤ 500) — the number of test cases. The description of the test cases follows.

The first line of the description of a test case contains an integer n (3 ≤ n ≤ 200 000) — the number of houses.

The i-th of the next n lines contains two integers x__i and y__i ( - 106 ≤ x__i, y__i ≤ 106) — coordinates of the i-th house. No two houses are located at the same point in the same test case. Limak lives in the first house.

The sum of n won't exceed 200 000.

输入的第一行包含一个整数 $T$（$1 \leq T \leq 500$）——测试用例的数量。随后是各测试用例的描述。

每个测试用例的描述以一行开始，该行包含一个整数 $n$（$3 \leq n \leq 200\,000$）——房屋的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^6 \leq x_i, y_i \leq 10^6$）——第 $i$ 座房屋的坐标。在同一测试用例中，任意两座房屋不会位于同一点。Limak 住在第一座房屋中。

所有测试用例的 $n$ 值之和不超过 $200\,000$。

Print one real value, denoting the area of the set of points that are possible new placements of Limak's house.

Your answer will be considered correct if its absolute or relative error doesn't exceed 10 - 6. More precisely, let the jury's answer be b, and your answer be a. Then your answer will be accepted if and only if .

输出一个实数值，表示 Limak 的房子所有可能新位置构成的点集的面积。

若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。更准确地说，设出题方的正确答案为 $b$，你的答案为 $a$，则当且仅当

时，你的答案会被接受。

In the sample test, there are 4 test cases.

In the first test case, there are four houses and Limak's one is in (5, 3). The set of valid new placements form a triangle with vertices in points (0, 1), (10, 1) and (3, 51), without its sides. The area of such a triangle is 250.

In the second test case, the set of valid new placements form a rectangle of width 50 000 and height 2 000 000. Don't forget that the new placement must be inside the big square that represents Bearland.

In the third test case, the three given points are collinear. Each cross product is equal to 0 and it should be 0 after the relocation as well. Hence, Limak's new house must lie on the line that goes through the given points. Since it must also be inside the big square, new possible placements are limited to some segment (excluding the two points where the other houses are). The area of any segment is 0.

在样例测试中，共有 4 个测试用例。

在第一个测试用例中，共有四座房屋，Limak 的房屋位于点 $(5,\,3)$。所有合法的新位置构成一个顶点为 $(0,\,1)$、$(10,\,1)$ 和 $(3,\,51)$ 的三角形（不包含其三条边）。该三角形的面积为 $250$。

在第二个测试用例中，所有合法的新位置构成一个宽为 $50\,000$、高为 $2\,000\,000$ 的矩形。请注意：新位置必须位于代表 Bearland 的大正方形内部。

在第三个测试用例中，给定的三个点共线。每个叉积均等于 $0$，且重定位后也应保持为 $0$。因此，Limak 的新房屋必须位于经过这三个给定点的直线上。又因新位置还必须位于大正方形内部，故所有可能的新位置被限制在某一条线段上（不包括另外两座房屋所在的位置）。任意线段的面积均为 $0$。