/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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 の凸包の面積を求めてください。ただし、凸包が空集合、1 点集合または線分である場合、その面積は 0 とします。
凸包の定義
\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 です。
