#P1870. Zju2361 Area

    ID: 892 传统题 1000ms 64MiB 尝试: 8 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-直线相交有理数精确运算自定义排序规则叉积半边面遍历鞋带公式浮点补偿求和

Zju2361 Area

Areas

题目描述

平面上有 NN 条两两不同的直线,它们会将整个平面划分成若干个区域,其中一些区域面积有限,另一些区域面积无限。

对于每组数据,你需要求出所有有限区域的面积。

由于浮点数计算可能产生精度误差,面积不超过 10−810^{-8} 的区域不计入答案。

输入格式

第一行一个整数 TT,表示测试数据组数。

接下来依次给出 TT 组数据。对于每组数据:

  • 第一行一个整数 NN,表示直线数量,1≤N≤801\le N\le 80;
  • 接下来 NN 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示一条经过点 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2) 的直线。两个点保证不同。

所有坐标的绝对值均不超过 10210^2,并保证任意两条直线不重合。

输出格式

对于每组数据:

首先输出一个整数 KK,表示这些直线划分出的有限区域数量。

接下来输出 KK 个实数,每个数单独一行,表示各有限区域的面积,并按非递减顺序排列。

答案允许的绝对误差为 10−410^{-4}。面积不超过 10−810^{-8} 的区域不应计入答案。

各组数据的输出直接依次给出即可;组间是否额外输出空行不影响评测。

样例输入

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

数据范围

对于每组数据:

  • 1≤N≤801\le N\le 80;
  • ∣x1∣,∣y1∣,∣x2∣,∣y2∣≤102|x_1|,|y_1|,|x_2|,|y_2|\le 10^2;
  • 每条直线由两个不同的点确定;
  • 任意两条直线不重合。