#P18326. Convex Hull of Intersections
Convex Hull of Intersections
Convex Hull of Intersections
标准输入、标准输出。
在 平面上有 条直线。第 条直线 的方程为
令 为这些直线的所有两两交点组成的集合,即
$$P=\{p\in\mathbb R^2\mid \exists i\ne j,\ p\in\ell_i,\ p\in\ell_j\}.$$求 的凸包面积。如果凸包为空集、单个点或一条线段,面积视为 。
共有 组测试数据,请分别求解。
凸包的定义
有限点集 的凸包定义为
$$\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\}.$$输入格式
第一行一个整数 。
每组测试数据的第一行一个整数 ,接下来 行,第 行三个整数 。
输出格式
输出 行,第 行表示第 组测试数据的答案。
只要输出值与实际答案的绝对误差或相对误差不超过 ,就认为正确。
数据范围
- ;
- ;
- ;
- 或 ;
- 任意两条直线在几何上不同;
- 所有测试数据的 之和不超过 ;
- 所有输入值均为整数。
样例输入 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
样例说明
第一组测试数据中,凸包是依次连接 的三角形,面积为 。原题配图如下,紫色区域为凸包。

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