算法导论上的原题
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))
我粗略地看材料上说好像可以推导出什么定理,在 3w 还是 6w 内寻找即可。我没那么想,而是直接从中心开始向两侧找,不断地更新 min 值,当发现点的横坐标的距离都已经大于 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'; } }
这题我真是佛了,涉及到 double 的题显然开一个 special judge 更好吧……研究了半天数据,我输出了个 0.01,答案里是 0.00 我就错了。结果我把 long double 改成 double 就对了
算法导论上的原题
我粗略地看材料上说好像可以推导出什么定理,在 3w 还是 6w 内寻找即可。我没那么想,而是直接从中心开始向两侧找,不断地更新
min
值,当发现点的横坐标的距离都已经大于min
的时候,就说明不可能再有更小的点对了。这题我真是佛了,涉及到 double 的题显然开一个 special judge 更好吧……研究了半天数据,我输出了个 0.01,答案里是 0.00 我就错了。结果我把 long double 改成 double 就对了