CF771F Bear and Isomorphic Points

Bearland 是一个平面上的大正方形。它包含所有坐标的绝对值不超过 $10^{6}$ 的点。 Bearland 中有 $n$ 栋房子，第 $i$ 栋房子位于点 $(x_{i},y_{i})$。这 $n$ 个点两两不同，但其中某些子集可能共线。 Bear Limak 住在第一栋房子里。他想要拆掉自己的房子，并在 Bearland 的某处重新建一所房子。 熊们不喜欢大的变动。对于任意三个点（房子）$p_{i}$、$p_{j}$ 和 $p_{k}$，它们的叉积 $(p_{j}-p_{i})×(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})×(b_{x},b_{y})=a_{x}·b_{y}-a_{y}·b_{x}$$ 设想 Limak 可选建房的新位置的集合。你需要计算这些点的面积。 形式化地讲，假设 Limak 随机选择新房子的位置（每个坐标独立且均匀地从区间 $[-10^{6},10^{6}]$ 中选取）。设 $p$ 为新址合法的概率，$S$ 为 Bearland 的面积（$S=4·10^{12}$）。你需要求出 $p·S$。

第一行输入一个整数 $T$（$1 \leq T \leq 500$）——表示测试用例数。接下来是每个测试用例的描述。 每个测试用例的第一行输入一个整数 $n$（$3 \leq n \leq 200000$）——表示房子的数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_{i}$ 和 $y_{i}$（$-10^{6} \leq x_{i},y_{i} \leq 10^{6}$），表示第 $i$ 栋房子的坐标。保证同一测试用例内没有两栋房子在同一位置。Limak 住在第一栋房子里。 所有测试用例中 $n$ 的总和不超过 $200000$。

输出一个实数，表示 Limak 新房子的所有可能位置的面积。 你的答案将在绝对误差或相对误差不超过 $10^{-6}$ 时被认为是正确的。更准确地说，设标准答案为 $b$，你的答案为 $a$，只有当 $|a-b| \leq 10^{-6} \max(1,|b|)$ 时答案才会被接受。

在样例测试中，共有 $4$ 组测试数据。 第一组中有四栋房子，Limak 的房子在 $(5,3)$。所有合法新位置组成一个以点 $(0,1)$、$(10,1)$、$(3,51)$ 为顶点（三边不包括在内）的三角形。这样的三角形面积为 $250$。 第二组中，合法的新位置组成一个宽 $50000$、高 $2000000$ 的矩形。注意新家必须在 Bearland 的大正方形内。 第三组中，给出的三点共线。所有叉积均为 $0$，新家也必须保证叉积为 $0$。因此，Limak 新家必须在三点共线的直线上。由于也要在大正方形内，所有可选新位置仅落在某条线段上（且不包括其他房子的两个点）。任何线段的面积都是 $0$。 由 ChatGPT 5 翻译