沙龙之《铁路连线问题》解题报告
   
                          福州一中 严寒凝

[解题思路]

  本题是一道简单的几何算法和分治策略相结合的题目。
  我们先用与Graham扫描法相类似的方法对于题目给出的点进行顺时针或逆时针排序,然后找出一点y坐标值最低的点记为V1,按顺序扫描这些点,累加所扫描到的人文景观和自然景观的个数,(注意:V1也要统计在内),直到扫描到的一点Vj,使人文景观和自然景观的个数相等,恰好可以与V1相搭配,我们就在V1,Vj之间建立一条铁路连先,这样原本排好序的集合(V1,V2…………VN)就可以化为两个更小的集合(V2……Vj-1)和(Vj+1……Vn),可以递归的求解。

  
  
  
  
  
  

   

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有