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