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} 什么的。

代码。注意精度问题。

 

 

 

 

 

 

 

 

JLOI2010 铁人双项比赛

我们有一个式子

t_i=\frac{k\left( v_{2i}-v_{1i} \right)}{v_{1i}v_{2i}}+\frac{s}{v_{2i}}

然后把 k 看做 x 轴,把 t 看作 y 轴,就是 n 条直线。

嗯,对于前 n-1 条求半平面交(注意直线对应的半平面是右侧)。

对于最后一条直线,最优的 k 是与这个凸包相切的时候。

而且显然 k 只会在端点处取到,所以直接二分找到斜率最近似的直线然后算一下答案即可。

注意最优的 k 为负的时候要调整为 0 并判定是否有解。