题面 根据题目要求, 求的是两组点之间的最短距离, 在求距离的时候把同一组里面点之间的距离看做inf就变成一个普通的平面最近点对问题. 平面最近点对问题用分治做, 先把点按照横坐标排序, 以中间的点为分界不断分成两个区间, 直到区间内只剩2个点, 直接返回答案, 然后再考虑点对横跨区间的情况, $ O(N^2)$枚举可能成为答案的点对. 优化就在这…