这题是判断线段相交，我的做法是枚举，由于题目数据中除了宝藏所在的点Point tar是浮点数，其余坐标全为整数，因此我采用的方法是把最外层每条边上的坐标的x或y坐标记录下来并排序，比如记录x=0的所有的点的y坐标在up[]数组中，其中，up[0]初始化为0。排序后，对每个数组中元素，将tar与(0,up[i]+0.5)组成一条边，判断它与每条边的交点数目即可，最后结果取最小值。
由于边的数目较小，因此这样做也蛮快的~~
代码copy下模板的就好了，注意，没有三面墙在同一交点，也就是说不存在不规范相交的情况，模板可以适当的改动~~
posted on 2009-06-29 12:48
古月残辉 阅读(435)
评论(0) 编辑 收藏 引用 所属分类:
计算几何