#P4541. 第2题-城市信号塔的最小距离
-
1000ms
Tried: 49
Accepted: 10
Difficulty: 7
所属公司 :
华为
时间 :2025年1月7日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>分治算法
第2题-城市信号塔的最小距离
解题思路
核心做法(分治 + 归并按 y 排序):
- 先按
x坐标排序所有点。 - 递归把点集分成左右两半,分别求出左右内部的最小距离平方
d。 - 在合并阶段,把当前区间按
y坐标归并排序(保证递归返回后区间内点按y有序)。 - 只需检查“中线附近”宽度为
sqrt(d)的条带(strip):满足(x-midx)^2 < d的点。 - 条带内点按
y有序后,对每个点只需向后检查y差平方小于d的少量点(理论保证常数个),更新最小值。
最终得到全局最小距离平方。
复杂度分析
- 时间复杂度:
O(n log n)(每层分治做一次线性归并与条带检查,总层数log n) - 空间复杂度:
O(n)(辅助数组用于归并)
代码实现
Python
import sys
def closest_pair(points):
# points: 已按 x 排序的点列表 [(x,y), ...]
n = len(points)
tmp = [None] * n # 归并时的临时数组
def solve(l, r):
# 计算 points[l:r] 的最近距离平方,并保证 points[l:r] 按 y 排序
if r - l <= 3:
# 小规模直接暴力
best = 1 << 62
for i in range(l, r):
x1, y1 = points[i]
for j in range(i + 1, r):
x2, y2 = points[j]
dx = x1 - x2
dy = y1 - y2
d = dx * dx + dy * dy
if d < best:
best = d
# 按 y 排序,方便上层归并
points[l:r] = sorted(points[l:r], key=lambda p: p[1])
return best
m = (l + r) // 2
midx = points[m][0]
d = solve(l, m)
dr = solve(m, r)
if dr < d:
d = dr
# 归并:把两段按 y 有序的数组合并
i, j, k = l, m, l
while i < m and j < r:
if points[i][1] <= points[j][1]:
tmp[k] = points[i]
i += 1
else:
tmp[k] = points[j]
j += 1
k += 1
while i < m:
tmp[k] = points[i]
i += 1
k += 1
while j < r:
tmp[k] = points[j]
j += 1
k += 1
points[l:r] = tmp[l:r]
# 收集条带点:只取 (x-midx)^2 < d 的点
strip = []
for t in range(l, r):
dx = points[t][0] - midx
if dx * dx < d:
strip.append(points[t])
# 条带按 y 已有序,只需检查后面 y 距离足够近的点
s = len(strip)
for a in range(s):
x1, y1 = strip[a]
b = a + 1
while b < s:
dy = strip[b][1] - y1
if dy * dy >= d:
break
dx = strip[b][0] - x1
dist = dx * dx + dy * dy
if dist < d:
d = dist
b += 1
return d
points.sort() # 按 x 排序
return solve(0, n)
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
points = []
idx = 1
for _ in range(n):
x = int(data[idx]); y = int(data[idx + 1])
idx += 2
points.append((x, y))
print(closest_pair(points))
if __name__ == "__main__":
main()
Java
import java.io.*;
import java.util.*;
public class Main {
static class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
}
// 按 x 排序的点数组
static Point[] pts;
// 归并按 y 的临时数组
static Point[] tmp;
// 读入指针
static int p = 0;
// 简单快读:从字节数组里读一个整数(默认输入合法)
static int nextInt(byte[] a) {
while (p < a.length && a[p] <= ' ') p++;
int sign = 1;
if (a[p] == '-') { sign = -1; p++; }
int v = 0;
while (p < a.length && a[p] > ' ') {
v = v * 10 + (a[p] - '0');
p++;
}
return v * sign;
}
static long closestPair(Point[] points) {
pts = points;
// 按 x 排序(若 x 相同按 y 排)
Arrays.sort(pts, (a, b) -> a.x != b.x ? a.x - b.x : a.y - b.y);
tmp = new Point[pts.length];
return solve(0, pts.length);
}
// 计算 pts[l:r) 的最近距离平方,并保证 pts[l:r) 按 y 排序
static long solve(int l, int r) {
if (r - l <= 3) {
// 小范围直接暴力
long best = Long.MAX_VALUE;
for (int i = l; i < r; i++) {
for (int j = i + 1; j < r; j++) {
long dx = (long) pts[i].x - pts[j].x;
long dy = (long) pts[i].y - pts[j].y;
long d = dx * dx + dy * dy;
if (d < best) best = d;
}
}
// 小段按 y 排序,方便上层合并
Arrays.sort(pts, l, r, Comparator.comparingInt(o -> o.y));
return best;
}
int m = (l + r) >>> 1;
int midx = pts[m].x;
// 分治求左右最小值
long d = solve(l, m);
long dr = solve(m, r);
if (dr < d) d = dr;
// 归并:两段按 y 有序合并
int i = l, j = m, k = l;
while (i < m && j < r) {
if (pts[i].y <= pts[j].y) tmp[k++] = pts[i++];
else tmp[k++] = pts[j++];
}
while (i < m) tmp[k++] = pts[i++];
while (j < r) tmp[k++] = pts[j++];
for (int t = l; t < r; t++) pts[t] = tmp[t];
// 收集条带点:只保留 (x-midx)^2 < d 的点(此时按 y 已有序)
Point[] strip = new Point[r - l];
int s = 0;
for (int t = l; t < r; t++) {
long dx = (long) pts[t].x - midx;
if (dx * dx < d) strip[s++] = pts[t];
}
// 条带检查:只看 y 距离平方 < d 的少量后续点
for (int a = 0; a < s; a++) {
for (int b = a + 1; b < s; b++) {
long dy = (long) strip[b].y - strip[a].y;
if (dy * dy >= d) break;
long dx = (long) strip[b].x - strip[a].x;
long dist = dx * dx + dy * dy;
if (dist < d) d = dist;
}
}
return d;
}
public static void main(String[] args) throws Exception {
// 读取全部输入(n 最大 1e5,这样读很快)
byte[] a = System.in.readAllBytes();
p = 0;
int n = nextInt(a);
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = nextInt(a);
int y = nextInt(a);
points[i] = new Point(x, y);
}
long ans = closestPair(points);
System.out.print(ans);
}
}
C++
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
};
static vector<Point> pts;
static vector<Point> tmp;
// 计算 pts[l:r) 的最近距离平方,并保证 pts[l:r) 按 y 排序
long long solve(int l, int r) {
if (r - l <= 3) {
long long best = (1LL << 62);
for (int i = l; i < r; i++) {
for (int j = i + 1; j < r; j++) {
long long dx = 1LL * pts[i].x - pts[j].x;
long long dy = 1LL * pts[i].y - pts[j].y;
long long d = dx * dx + dy * dy;
if (d < best) best = d;
}
}
sort(pts.begin() + l, pts.begin() + r, [](const Point& a, const Point& b){
return a.y < b.y;
});
return best;
}
int m = (l + r) / 2;
int midx = pts[m].x;
long long d = solve(l, m);
long long dr = solve(m, r);
if (dr < d) d = dr;
// 归并按 y
int i = l, j = m, k = l;
while (i < m && j < r) {
if (pts[i].y <= pts[j].y) tmp[k++] = pts[i++];
else tmp[k++] = pts[j++];
}
while (i < m) tmp[k++] = pts[i++];
while (j < r) tmp[k++] = pts[j++];
for (int t = l; t < r; t++) pts[t] = tmp[t];
// 条带点(按 y 已有序)
vector<Point> strip;
strip.reserve(r - l);
for (int t = l; t < r; t++) {
long long dx = 1LL * pts[t].x - midx;
if (dx * dx < d) strip.push_back(pts[t]);
}
// 检查后续 y 足够近的点
for (int a = 0; a < (int)strip.size(); a++) {
for (int b = a + 1; b < (int)strip.size(); b++) {
long long dy = 1LL * strip[b].y - strip[a].y;
if (dy * dy >= d) break;
long long dx = 1LL * strip[b].x - strip[a].x;
long long dist = dx * dx + dy * dy;
if (dist < d) d = dist;
}
}
return d;
}
long long closest_pair(vector<Point>& points) {
pts = points;
sort(pts.begin(), pts.end(), [](const Point& a, const Point& b){
if (a.x != b.x) return a.x < b.x;
return a.y < b.y;
});
tmp.assign(pts.size(), Point{0, 0});
return solve(0, (int)pts.size());
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].x >> points[i].y;
}
cout << closest_pair(points) << "\n";
return 0;
}
题目内容
某城市计划在多个地点建立信号塔,所有信号塔的覆盖范围均为圆形,现给定所有信号塔的坐标(二维平面上的点),要求检测信号塔间的距离 (x1−x2)2+(y1−y2)2,请返回所有信号塔间的最小距离。
输入描述
第一行为整数 n(2≤n≤100000),表示表示信号塔数量。
接下来 n 行,每行包含两个整数 x(−100000≤x≤100000) 和 y(−100000≤y≤100000),以空格分隔,表示信号塔的坐标。
输出描述
一个整数,表示所有信号塔间的最小距离。
样例1
输入
5
0 0
0 5
3 4
3 5
3 6
输出
1
说明
最近的点对是 (3,4) 和 (3,5),距离为 (3−3)2+(5−4)2=1 。
样例2
输入
4
0 0
0 1
1 0
1 1
输出
1
说明
最近的点对是 (0,0)、(0,1) 和 (0,0)、(1,0),距离为 (0−0)2+(1−0)2=1
样例3
输入
2
0 0
1 1
输出
2
说明
最近的两个点是 (0,0) 和 (1,1),距离为 (1−0)2+(1−0)2=2 。