随笔-20  评论-16  文章-36  trackbacks-0
      这题是判断线段相交,我的做法是枚举,由于题目数据中除了宝藏所在的点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 古月残辉 阅读(425) 评论(0)  编辑 收藏 引用 所属分类: 计算几何

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理