← 返回题目列表

AtCoder · tupc2024_g

G. 交叉点的凸包

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

配点 : 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 。