您的当前位置:首页正文

poj2826 An Easy Problem?!(计算几何)

2024-11-07 来源:个人技术集锦

•思路

找不能收集到雨水的情况

我们令线段较高的点为s点,较低的点为e点

①两条木块没有交点

②平行或重合

③至少有一条木块水平(雨水会滑落)

④形成覆盖,如"$\wedge $","人",还有比较难想的上边长下边短的情况

  •  其中形成"$\wedge$"型和"人"型 都是两条线段的交点比两条线段中较低的s点同高,

      也就是不大于较高的s点

  • 上长下短的覆盖是两个s点都大于交点而不能存水的唯一情况

     如上图,我们可以在a.x出从b上引一条竖直线,看是否与a有交点,如果有说明覆盖了

能收集到雨水的情况要注意 水面与较低的s点水平

•代码

转载于:https://www.cnblogs.com/MMMinoz/p/11492764.html

Top