Bearland是位面上的一个大正方形。它包含坐标绝对值不超过106的所有点。
Bearland 有 n 栋房子。其中第 i 个位于点 (xi, yi)。这 n 个点是不同的,但它们的某些子集可能是共线的。
Bear Limak 住在第一栋房子里。他想毁掉自己的房子,并在贝尔兰德的某个地方建造一所新房子。
熊不喜欢大的变化。对于每三个点(房屋)pi、pj、pk,其叉积(pj - pi)×(pk - pi)的符号在搬迁前后应相同。如果它是负/正/零,它仍然应该分别是负/正/零。所有索引三元组 (i, j, k) 都应满足此条件,可能彼此相等或不等于 1。此外,不允许 Limak 在其他房屋已存在的位置建造房屋(但可以是他的旧房屋所在的位置)。
在上面的公式中,我们将点(ax, ay)和(bx, by)的差值和叉积定义为:
(ax, ay) - (bx, by) = (ax - bx, ay - by),
(ax, ay) × (bx, by) = ax·by - ay·bx。
考虑利马克房子的一组可能的新布局。您的任务是找到该组点的面积。
正式来说,假设 Limak 随机选择新的位置(每个坐标都是从区间 [ - 106, 106] 中独立、均匀地随机选择)。令 p 表示获得新房允许安置的概率。令 S 表示 Bearland 的面积 (S = 4·1012)。你的任务是找到p·S。
输入
输入的第一行包含一个整数 T (1 ≤ T ≤ 500) — 测试用例的数量。测试用例的描述如下。
测试用例描述的第一行包含一个整数 n (3 ≤ n ≤ 200 000) – 房屋数量。
接下来 n 行的第 i 行包含两个整数 xi 和 yi (- 106 ≤ xi, yi ≤ 106) — 第 i 个房子的坐标。在同一测试用例中,没有两栋房屋位于同一点。利马克住在第一栋房子里。
n 的总和不会超过 200 000。
输出
打印一个实数值,表示 Limak 房子可能的新位置的一组点的面积。
如果您的答案的绝对或相对误差不超过 10 - 6,则认为您的答案是正确的。更准确地说,让陪审团的答案为 b,您的答案为 a。那么当且仅当 $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$ 时,你的答案才会被接受。
示例
输入 #1
4 4 5 3 0 1 10 1 3 51 3 -999123 700000 -950000 123456 -950000 987654 3 2 3 10 -1 -4 6 5 1 3 5 2 6 1 4 4 -3 3
输出 #1
250.000000000000 100000000000.000000000000 0.000000000000 6.562500000000
注意
样本测试中,有4个测试用例。
在第一个测试用例中,有四栋房子,Limak 的房子在 (5, 3) 中。这组有效的新放置形成一个三角形,其顶点位于点 (0, 1)、(10, 1) 和 (3, 51),但没有边。这样一个三角形的面积是250。
在第二个测试用例中,一组有效的新放置形成一个宽度为 50 000、高度为 2 000 000 的矩形。不要忘记,新放置必须位于代表 Bearland 的大正方形内。
在第三个测试用例中,三个给定点共线。每个叉积都等于 0,并且在重定位后也应该为 0。因此,利马克的新房子必须位于经过给定点的线上。由于它也必须位于大广场内,因此新的可能放置仅限于某些部分(不包括其他房屋所在的两个点)。任意线段的面积都是0。