1126. 最近点对

SmallY

算法导论上的原题

from math import sqrt

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance(self, other):
        return sqrt((self.x-other.x)*(self.x-other.x)+(self.y-other.y)*(self.y-other.y))

    def __str__(self):
        return str(self.x)+" "+str(self.y)


def calMin(L, left, right):
    d = 0x7fffffff
    for i in range(left, right-1):
        for j in range(i+1, min(right, i+8)):
            temp = L[i].distance(L[j])
            d = min(temp, d)
    return d

def cut(Lx, left, right, Ly):
    if right-left < 4:
        return calMin(Lx, left, right)
    middle = (left+right)//2
    midX = Lx[middle].x
    Lyl = []; Lyr = []
    for point in Ly:
        if point.x < midX:
            Lyl.append(point)
        else:
            Lyr.append(point)
    d1 = cut(Lx, left, middle, Lyl)
    d2 = cut(Lx, middle, right, Lyr)
    d = d1 if d1 < d2 else d2
    return merge(Lx, left, right, d, Ly)

def merge(L, left, right, d, Ly):
    middle = (left+right)//2
    midX = L[middle].x
    tempL = []
    for point in Ly:
        if midX-d <= point.x <= midX+d:
            tempL.append(point)
    d2 = calMin(tempL, 0, len(tempL))
    return min(d, d2)


while True:
    N = int(input())
    if N == 0:
        break
    Lx = []
    for _ in range(N):
        x, y = map(float, input().split())
        Lx.append(Point(x, y))
    Lx.sort(key=lambda point: point.x)
    Ly = Lx[:]
    Ly.sort(key=lambda point: point.y)
    print("%.2f"%(cut(Lx, 0, N, Ly)/2))
Deuchie

我粗略地看材料上说好像可以推导出什么定理,在 3w 还是 6w 内寻找即可。我没那么想,而是直接从中心开始向两侧找,不断地更新 min 值,当发现点的横坐标的距离都已经大于 min 的时候,就说明不可能再有更小的点对了。

#include "bits/stdc++.h"
using u64 = uint64_t;

struct Point {
    double x, y;
};

double static square(double a) { return a * a; }

double static distance(Point a, Point b) { return sqrt(square(a.x - b.x) + square(a.y - b.y)); }

double static min_distance(std::vector<Point>::iterator bg, std::vector<Point>::iterator ed) {
    auto const kNum = ed - bg;
    // Make sure kNum > 1.
    if (kNum == 2) {
        return distance(*bg, *(bg + 1));
    }
    if (kNum == 3) {
        return std::min({distance(*bg, *(bg + 1)), distance(*bg, *(bg + 2)), distance(*(bg + 1), *(bg + 2))});
    }
    auto const kMid = bg + kNum / 2;
    auto ret = std::min(min_distance(bg, kMid), min_distance(kMid, ed));
    for (auto i = kMid - 1, i_ed = bg - 1; i != i_ed; --i) {
        if (abs(i->x - kMid->x) > ret) {
            break;
        }
        for (auto j = kMid; j != ed; ++j) {
            if (abs(i->x - j->x) > ret) {
                break;
            }
            auto dis = distance(*i, *j);
            if (ret > dis) {
                ret = dis;
            }
        }
    }
    return ret;
}

int main() {
    std::cout << std::fixed;
    std::cout.precision(2);
    for (u64 n; std::cin >> n, n;) {
        std::vector<Point> points(n);
        for (auto &i : points) {
            std::cin >> i.x >> i.y;
        }
        sort(points.begin(), points.end(),
             [](Point const &lhs, Point const &rhs) { return std::tie(lhs.x, lhs.y) < std::tie(rhs.x, rhs.y); });
        std::cout << min_distance(points.begin(), points.end())/ 2 << '\n';
    }
}
Deuchie

这题我真是佛了,涉及到 double 的题显然开一个 special judge 更好吧……研究了半天数据,我输出了个 0.01,答案里是 0.00 我就错了。结果我把 long double 改成 double 就对了

你当前正在回复 博客/题目
存在问题!