Skip to content

1299: Closest pair

题目

题目描述

给定 $n$ 个二维欧几里得平面上的点 $p_1, p_2, \dots, p_n$,请输出距离最近的两个点的距离。

Input

请从 stdin 读入。

输入第一行为一个正整数 $n (2 \leq n \leq 4\times 10^5)$,表示点数。

接下来 $n$ 行,第 $i$ 行为用空格隔开的整数 $x_i, y_i (-10^7 \leq x_i, y_i \leq 10 ^ 7)$,表示 $p_i = (x_i, y_i)$。

输入保证:没有两个坐标完全相同的点。

Output

请输出到 stdout 中。

输出一行,包含一个整数 $D^2$,表示距离最近的两个点的距离的平方

由于输入的点为整点,因此这个值一定是整数。

Sample Input

txt 2 -10000000 -10000000 10000000 10000000

txt 5 1 1 1 9 9 1 9 9 0 10

Sample Output

txt 800000000000000

txt 2

Constraints

Time Limit: 1s

Memory Limit: 128MB

数据一共有 50 组,可能会测得比较慢,请在 Running & Judging 的时候饮一杯茶。

Note

对于第二组样例,$(1, 9) (0, 10)$ 两个点最近,距离为 $\sqrt 2$,因此你需要输出 $2$。

本题参考 Python 实现如下。非常遗憾,我们的 OJ 不支持提交 Python。

请注意:为了实现简单,这份代码的时间复杂度是 $O(n \log ^ 2 n)$ 的。

```python class point: def init(self, x:int, y:int): self.x = x self.y = y def distance_2(self, other) -> int: return (self.x - other.x) 2 + (self.y - other.y) 2

def solve(a, l, r) -> int: # the square of closest distance between index range [l, r) if l + 1 >= r: return 2 64 # = INFINITY m = (l + r) // 2 ret = min(solve(a, l, m), solve(a, m, r)) strip = [] for i in range(l, r): if (a[i].x - a[m].x) 2 < ret: strip.append(a[i]) strip.sort(key=lambda p : p.y) for i in range(len(strip)): for j in range(i + 1, len(strip)): if (strip[i].y - strip[j].y) ** 2 >= ret: break ret = min(ret, strip[i].distance_2(strip[j])) return ret

n = int(input()) a = [] for i in range(n): x, y = map(int, input().split()) a.append(point(x, y)) a.sort(key=lambda p : p.x) print(solve(a, 0, n)) ```

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!