#P18326. Convex Hull of Intersections

Convex Hull of Intersections

Convex Hull of Intersections

标准输入、标准输出。

在 xyxy 平面上有 NN 条直线。第 ii 条直线 ℓi\ell_i 的方程为

aix+biy+ci=0.a_ix+b_iy+c_i=0.

令 PP 为这些直线的所有两两交点组成的集合,即

$$P=\{p\in\mathbb R^2\mid \exists i\ne j,\ p\in\ell_i,\ p\in\ell_j\}.$$

求 PP 的凸包面积。如果凸包为空集、单个点或一条线段,面积视为 00。

共有 TT 组测试数据,请分别求解。

凸包的定义

有限点集 S={x1,…,x∣S∣}S=\{x_1,\ldots,x_{|S|}\} 的凸包定义为

$$\operatorname{conv}(S)= \left\{\sum_{i=1}^{|S|}\alpha_i x_i\ \middle|\ \sum_{i=1}^{|S|}\alpha_i=1,\ 0\le\alpha_i\le1\right\}.$$

输入格式

第一行一个整数 TT。

每组测试数据的第一行一个整数 NN,接下来 NN 行,第 ii 行三个整数 ai,bi,cia_i,b_i,c_i。

输出格式

输出 TT 行,第 ii 行表示第 ii 组测试数据的答案。

只要输出值与实际答案的绝对误差或相对误差不超过 10−510^{-5},就认为正确。

数据范围

  • 1≤T1\le T;
  • 2≤N≤1042\le N\le10^4;
  • ∣ai∣,∣bi∣,∣ci∣≤103|a_i|,|b_i|,|c_i|\le10^3;
  • ai≠0a_i\ne0 或 bi≠0b_i\ne0;
  • 任意两条直线在几何上不同;
  • 所有测试数据的 NN 之和不超过 2×1052\times10^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

样例说明

第一组测试数据中,凸包是依次连接 (8,6),(−4,0),(8,−6)(8,6),(-4,0),(8,-6) 的三角形,面积为 7272。原题配图如下,紫色区域为凸包。

第一组测试数据:四条直线的所有交点及其凸包

第二组测试数据中,三条直线互相平行,P=∅P=\varnothing,所以凸包面积为 00。原题配图如下。

第二组测试数据:三条互相平行的直线