随笔-20  评论-16  文章-36  trackbacks-0
      这两题几乎是一样的,都是求给定半径的圆能覆盖的最多点的个数。我想的方法是O(n^3)的,时间用的比较多……
      思路是枚举两两点,根据它们的坐标和半径求出圆心的坐标,再判断所有点是否在圆内,题目不难,公式较繁,细心点就行了,还有要注意至少能选一个点,以及斜率不存在等等边界的情况,我就wa了很多次……
      时间的话,有O(n^2lgn)的,网上搜到,看了下,是把每个点作为圆心,再求每个圆与其它圆的交,记录交点,再经过处理就可以得到在同一个圆内的点数,感觉也蛮繁的,就没去实现了……有兴趣自已搜,至于那些个100ms的大牛们什么思路,我也就不得得知了……
posted on 2009-06-29 16:28 古月残辉 阅读(984) 评论(0)  编辑 收藏 引用 所属分类: 计算几何

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