配点 : 100 点
問題文
xy 飞机上不同 N 有一条直线, i 第直线 以 \ell_i 是 给出了 a_i x + b_i y + c_i = 0 形式表示。 这些直线的所有交点的集合是 P 。更准确地说:
P = \{ p \in \mathbb{R}^2 \mid \exists i, j \in \{1, 2, \ldots, N\} \, \text{ s.t. } \, p \in \ell_i, \, p \in \ell_j, \, i \neq j \}
此时, P 的凸包面积。然而,如果凸包是空集、点集或线段,则其面积为 0 被记作。
凸包的定义
有限集合 S = \{ x_1, \ldots, x_{|S|} \} 的凸包 \text{conv}(S) 定义如下。
您将获得
\displaystyle \text{conv}(S) = \left\{ \sum_{i=1}^{|S|} \alpha_i x_i \, \middle\vert \, \sum_{i=1}^{|S|} \alpha_i = 1, \, 0 \leq \alpha_i \leq 1 \right\}
T 测试用例,因此请找到每个测试用例的答案。
制約
- 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
- 直線 \ell_i 和 在 \ell_j 不同(i \neq j)
- 1 包含在一个输入文件中 N 的总和是 2 \times {10}^5 以下
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
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
3 4 1 -1 -2 3 3 -6 -1 2 -4 1 2 4 3 3 0 5 5 0 18 1 0 7 3 314 159 -1 313 158 -1000 315 160 999
出力例 1
72.0 0 0.0016129032
1 在第二个测试用例中, P 的凸包是 它是一个按顺序连接 (8, 6), (-4, 0), (8, -6) 的三角形,它的面积是 72 。
2 在第二个测试用例中, 3 所有直线都是平行的,所以 P = \emptyset 。 因此, P 的凸包面积为 0 。
