← 返回题目列表

Codeforces · 771/F

F. 熊和同构点

中文机器翻译题面 查看原题

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。