我正在学习从算法的测试和我看到的问题，我不能应付几天。 所以，我写这里寻求帮助。
对于平面上给定两个不相交集 ：
G={(x_1^G, y_1^G), (x_2^G, y_2^G), ..., (x_n^G, y_n^G)}
D={(x_1^D, y_1^D), (x_2^D, y_2^D), ..., (x_n^D, y_n^D)}
Where for every 1 <= i, j <= n we have y_i^D < y_j^G, so G is above D.
找到一种有效的算法， counts the distance between them定义为：
d(G,D) = min{ d(a,b): a \in G and b\in D },
where d(a,b) = |x_a - x_b| + |y_a - y_b|
为O（n ^ 2）是微不足道的，所以它是不是答案。
我希望解决的办法是不要太用力，因为它是从材料到测试前审查。 任何人都可以帮忙吗？
我认为它会出现，这是一些常见的问题的一个特例。 但是，如果它是一个特例，也许该解决方案可以更容易？
有几种不同的方式为O做到这一点（N log n）的时间。
之一：计算的曼哈顿距离Voronoi图对于g点，并且建立一个基于该点位置的数据结构。 这需要为O（n log n）的时间。 对于每个d点，发现使用该点的位置的数据结构的最接近点ģ。 这需要每d点O（log n）的时间。 就拿你刚发现的对之间的距离最小，这就是你的答案。
第二：你能适应财富的算法解决这个问题; 只是一味的d和G点单独的二进制树。 恼人的种类来形容。
接下来的想法计算最近一为无穷大范数，这是最大的距离（| X1-X2 |，| Y1-Y2 |）。 你可以倾斜你的问题45度（代U = XY，V = X + Y）来获取到适当的形式。
三个（两个变量）：排序所有点的y坐标。 保持d，迄今所看到的最接近一对之间的距离。 我们会从顶部扫线下，维护两个二叉搜索树，G的点之一，d点之一。 当一个点d或更远的扫描线之上，我们从它的二叉搜索树中删除。 当点首先通过扫描线遇到的，说了d点，我们（1）检查摹二叉搜索树，看它是否具有其x坐标为新点的的d内的任何元素，更新必要的d， （2）将新点到D的二叉搜索树。 每个点只能导致二叉搜索树的操作加上额外的工作一定量的常数，所以扫描是O（n log n）的。 排序过，勿庸置疑，所以我们整体的时间复杂度是任意的。
你也许可以做一个分而治之的策略太工作基于类似的想法三个。
