100 #P1215. G54_4 半平面交 双端队列【计算几何】求半平面交的面积

G54_4 半平面交 双端队列【计算几何】求半平面交的面积

【题意】

在一个有限大(x,y104|x|,|y| \le 10^4)的平面坐标系上,给出 nn 个半平面(注意给出的半平面是有限的),每个半平面给出一条有向线段 (x1,y1)(x2,y2)(x1,y1) \to (x2,y2)

每个半平面的有效区域都是左侧。求这 nn 个半平面的交的面积。

【输入格式】

第一行一个整数 n(1n20000)n(1 \le n \le 20000)

下来 nn 个半平面。每个半平面一行四个整数 $x_1 \ y_1 \ x_2 \ y_2(|x_1|,|y_1|,|x_2|,|y_2| \le 100000)$。

【输出格式】

一行一个实数,即 nn 个半平面的交的面积(保留一位小数),如果有效面积不存在则输出 0.0

【样例输入1】

3
1 1  9 9
5 10  4 10
0 3 0 2

【样例输出1】

50.0

【样例输入2】

4
0 0  10 0
10 0  10 10
10 10 0 10
11 11 11 0

【样例输出2】

0.0