#P1870. Zju2361 Area
Zju2361 Area
Areas
题目描述
平面上有 条两两不同的直线,它们会将整个平面划分成若干个区域,其中一些区域面积有限,另一些区域面积无限。
对于每组数据,你需要求出所有有限区域的面积。
由于浮点数计算可能产生精度误差,面积不超过 的区域不计入答案。
输入格式
第一行一个整数 ,表示测试数据组数。
接下来依次给出 组数据。对于每组数据:
- 第一行一个整数 ,表示直线数量,;
- 接下来 行,每行四个整数 ,表示一条经过点 和 的直线。两个点保证不同。
所有坐标的绝对值均不超过 ,并保证任意两条直线不重合。
输出格式
对于每组数据:
首先输出一个整数 ,表示这些直线划分出的有限区域数量。
接下来输出 个实数,每个数单独一行,表示各有限区域的面积,并按非递减顺序排列。
答案允许的绝对误差为 。面积不超过 的区域不应计入答案。
各组数据的输出直接依次给出即可;组间是否额外输出空行不影响评测。
样例输入
1
5
0 0 1 0
1 0 1 1
1 1 0 1
0 1 0 0
0 0 1 1
样例输出
2
0.5000
0.5000
数据范围
对于每组数据:
- ;
- ;
- 每条直线由两个不同的点确定;
- 任意两条直线不重合。