Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

12/17
21:46
计算几何

[bzoj 4614] [Wf2016]Oil

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给定n条平行线段,每条线段的价值是它的长度。现在用一条直线贯穿最大价值的线段,求最大的价值。
N<=2000。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行一个数n表示线段数。家下来n行每行三个数x0,x1和y,表示线段(x0,y)-(x1,y)。
|x0|,|x1|<=10^6,1<=y<=10^6。线段无交。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出最大的价值。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

1
-100 180 20

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

280

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

可以看出最优方案一定经过了某条线段的某个端点,所以我们可以枚举每一个端点,那么一条线段就对应了一段斜率区间,看成插入和删除操作进行处理就可以了

要注意的是题目当中的“贯穿”是不能覆盖的,也就是这条直线不能平行于x轴

 

[bzoj 4614] [Wf2016]Oil