Posted on 2010-03-21 00:36
王之昊 阅读(207)
评论(0) 编辑 收藏 引用 所属分类:
pku
这道题模拟，已知一个支点，去寻找下一个支点，累加这期间的角度直到转到满意的角度为止。把绕支点的转动看成一个圆，把多边形的每条线段看成障碍物。现在来考虑一些特殊位置。
出题者应该会避免相切的数据。和当前木棍在同一直线上的特殊点，一种可以根据线段的中心确定它会不会阻挡。
另外一种连中心也在同一条直线上。这时认为在有木棍实体的那侧的特殊点不会阻挡，而另一侧会。
总的来说，障碍物（一条线段）他可能出现的位置是0~360。而难区分的是0度和360度。如果发现一个点落在0度或360度的位置时，通过判断障碍物在左边（包括平行的时候）还是在右边来确定会不会阻挡。
还可以通过让木棍转动一个小的角度，看一下是远离障碍物，还是和障碍物相交来确定是否会阻挡。