100 #P1215. G54_4 半平面交 双端队列【计算几何】求半平面交的面积
G54_4 半平面交 双端队列【计算几何】求半平面交的面积
【题意】
在一个有限大()的平面坐标系上,给出 个半平面(注意给出的半平面是有限的),每个半平面给出一条有向线段 。
每个半平面的有效区域都是左侧。求这 个半平面的交的面积。
【输入格式】
第一行一个整数 。
下来 个半平面。每个半平面一行四个整数 $x_1 \ y_1 \ x_2 \ y_2(|x_1|,|y_1|,|x_2|,|y_2| \le 100000)$。
【输出格式】
一行一个实数,即 个半平面的交的面积(保留一位小数),如果有效面积不存在则输出 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