题目大意
给出几个矩形对角端点坐标,求这些矩形整体覆盖的面积。
扫描线算法
整个平面被每个矩形的长边所在直线(以后简称“长线”)分成了几个部分,而整体覆盖面积则为每相邻的两个长线间夹的长度(以后简称“夹长”)以及长线所对应矩形长边在长线(以后简称“长线段”)中所占的长度之积的和。于是我们假设有一个扫描线从下往上扫。由排序得到夹长很容易,但是长线段长就要用线段树了。
给出几个矩形对角端点坐标,求这些矩形整体覆盖的面积。
整个平面被每个矩形的长边所在直线(以后简称“长线”)分成了几个部分,而整体覆盖面积则为每相邻的两个长线间夹的长度(以后简称“夹长”)以及长线所对应矩形长边在长线(以后简称“长线段”)中所占的长度之积的和。于是我们假设有一个扫描线从下往上扫。由排序得到夹长很容易,但是长线段长就要用线段树了。