[POJ3714]Raid[分治,平面最近点对]

题面

根据题目要求, 求的是两组点之间的最短距离, 在求距离的时候把同一组里面点之间的距离看做inf就变成一个普通的平面最近点对问题.

平面最近点对问题用分治做, 先把点按照横坐标排序, 以中间的点为分界不断分成两个区间, 直到区间内只剩2个点, 直接返回答案, 然后再考虑点对横跨区间的情况, $latex O(N^2)$枚举可能成为答案的点对.

优化就在这个”可能”的判断上, 因为点对横跨区间, 一个点对中的每个点横坐标到两区间分界点的水平距离都至多为当前答案ans, 才有可能距离比ans更短, 借此初步筛选可能的点. 其次, 把这些点按照纵坐标排序, 枚举的时候距离就有单调性, 可以及时break, 具体见代码.

注意坐标值有$latex 10^9$大, 要开long long不然会WA.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址