POJ2826计算几何、线段交点
题目
在平面中给出两条线段,问最多能接到多少从上至下的雨水。
解题思路
要能接到雨水,首先得满足两条线段相交形成‘V’型结构,相交大致有以下情况,比较难考虑到的有情况3、4:
来找四种情况的特征即可。方法很多,下面是一种可行方法
情况2:点1点2的y坐标相同
情况1:过点1作垂线与直线23交于点5,点5的y坐标小于直线14-23的交点坐标。
情况3、4:作点1的垂线交直线23于点5,判断点5点3上方还是下方即可。
判断方法很多,尽量减少运算次数、除法为优。
POJ的老编译CE太难受了,还有经典C++AC,G++WA
代码
1 |
|