AT_tupc2024_g Convex Hull of Intersections

在 $xy$ 平面上有 $N$ 条互不相同的直线，第 $i$ 条直线 $\ell_i$ 可以表示为 $a_i x + b_i y + c_i = 0$ 的形式。所有这些直线的交点的集合记为 $P$。更严格地说，定义如下： $$ P = \left\{ p \in \mathbb{R}^2 \mid \exists \, i, j \in \{1, 2, \ldots, N\} \text{ 且 } i \neq j, \, p \in \ell_i, \, p \in \ell_j \right\} $$ 请计算 $P$ 的凸包的面积。如果凸包为空集、只有一个点或是一条线段，则认为面积为 $0$。 凸包的定义 有限集合 $S = \{ x_1, \ldots, x_{|S|} \}$ 的凸包 $\text{conv}(S)$ 定义如下： $$ \text{conv}(S) = \left\{ \sum_{i=1}^{|S|} \alpha_i x_i \,\middle|\, \sum_{i=1}^{|S|} \alpha_i = 1, \; 0 \leq \alpha_i \leq 1 \right\} $$ 给定 $T$ 组测试数据，请分别给出每组的答案。

输入按以下格式从标准输入读入。 > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 其中，$\text{case}_i$ 表示第 $i$ 个测试用例，每个测试用例的格式如下： > $N$ > $a_1$ $b_1$ $c_1$ > $a_2$ $b_2$ $c_2$ > $\vdots$ > $a_N$ $b_N$ $c_N$

输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例的答案。 当且仅当你的答案与标准答案在绝对误差或相对误差不超过 $10^{-5}$ 时，会被判定为正确。

### 样例解释 1 第 $1$ 个测试用例中，$P$ 的凸包是依次连接 $(8, 6), (-4, 0), (8, -6)$ 形成的三角形，其面积为 $72$。 第 $2$ 个测试用例，三条直线均互相平行，因此 $P = \emptyset$。所以 $P$ 的凸包面积为 $0$。   ### 数据范围 - $1 \leq T$ - $2 \leq N \leq 10^4$ - $|a_i|, |b_i|, |c_i| \leq 10^3$ - 至少有一个 $a_i \neq 0$ 或 $b_i \neq 0$ - 任意 $i \neq j$，直线 $\ell_i$ 与 $\ell_j$ 不相同 - 同一份输入文件中所有 $N$ 的总和不超过 $2 \times 10^5$ - 输入均为整数 由 ChatGPT 5 翻译