CQOI2005 三角形面积并

计算几何 × 扫描线入门题

首先把线段都搞出来,然后求所有线段交点的横坐标(包括三角形顶点)并且去重。

也就是求出所有线段交点的 x 轴垂线。

然后把数据排序,枚举相邻的一对垂线,这个时候差不多是这样的

沃日,这图太大了。。 iPad Mini 2 的 Retina 屏真带劲。。

然后你会发现枚举的垂线中间夹着的是若干梯形。假设枚举的是 x_1,x_2 ,那么我用 \frac{(x_1+x_2)}{2}=0 这个“中间的直线”去切割这截出来的一大堆梯形。

显然同一个三角形在 x_1,x_2 之间的部分会被这个直线穿两次,如果我们把下面那次看做一个 ( ,上面的看做 ) ,这就是求所有 至少被一对括号包括起来 的部分的长度。然后用这个长度乘以 x_2-x_1 就是这部分的答案。

还有一点细节是比如像绿色那货,它有条直线是和 x 垂直的,因为特判难写难调,精度要求不高,那条直线直接给他加上一个 OFFSET 带走。比如变成斜率 k=10^{-5} 什么的。

代码。注意精度问题。