黑书上计算几何第二个例题，到现在才做到。
思路黑书上已经讲的很清楚了，我讲下实现的细节。一开始我是打算用把当前考虑的线段延长的方法来做的，可是发现可能它不与任何线段相交，但它也不在管道内，这个很容易理解，因此换个思路，对于每个线段，对每个横坐标，判断它的延长线在该处的y值是不是在管道内，如果是，则考虑下一个X，否则计算交点，由于计算交点的时候只要考虑这条线段右边端点的右边情况就可以了，因为如果在右端点之前相交，光线根本到达不了那。而且如果计算出来的y比第k段上面的y大，说明交点是在k-1~k段的上管道，否则在k-1~k的下管道。
要特别注意的两点，一个是初始化最远点坐标时，不能习惯性的初始化为0，我为此wa了一次，另外精度很重要，在判断是否在管道内的时候，要用eps，而且eps要设的足够小，我没设wa了一次，设为1e-6又wa了一次……设为1e-8才能过~~
posted on 2009-07-01 22:09
古月残辉 阅读(1262)
评论(0) 编辑 收藏 引用 所属分类:
计算几何