SGOI12之《土地划分》解题报告
   


  题意描述

  农场主拥有一块土地,土地中有篱笆隔开,要我们求出每类土地包含的线段数以及该类土地的数目。
  注意:1.边界线段不会超过所在土地地拐角。
     2.每块土地至少一条边与多边形重合。


  算法分析

  由于有注意事项1与2的提示,我们很容易设计如下算法:
  1.沿着外墙逆时针找出多边形的外轮廓,
  2.因为每块土地至少一条边与多边形重合,所以我们可以从外轮廓的每一条边开始,按顺时针方向搜索每个小多边形。注意:有可能一个小多边形与土地轮廓的两条或两条以上的边重合,所以搜索时要注意判重。

  参考程序

  
   
   
     
     
  
  
   
  

   

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