QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#601479 | #142. 平面最近点对 | learn_bw | 0 | 0ms | 0kb | Python3 | 2.2kb | 2024-09-30 01:04:57 | 2024-09-30 01:04:57 |
answer
import math
def distance(p1, p2):
return math.sqrt((p1[0]-p2[0])**2+(p1[1]-p2[1])**2)
def closest_pair(points):
# 按照横坐标排序
points.sort(key=lambda point:point[0])
def _closest_pair(px, py):
# 小于等于3个点,不需要分治,直接计算
if len(px) <= 3:
min_dist = float('inf')
best_pair = None
for i in range(len(px)):
for j in range(i+1,len(px)):
dist = distance(px[i], px[j])
if dist < min_dist:
min_dist = dist
best_pair = (px[i], px[j])
return min_dist, best_pair
# 找到横坐标中间点
mid = len(px)//2
Qx = px[:mid]
Rx = px[mid:]
midpoint = px[mid][0]
# 找到按纵坐标排序的列表里面横坐标小于等于midpoint的点
Qy = [p for p in py if p[0] <= midpoint]
Ry = [p for p in py if p[0] > midpoint]
dl, pair_l = _closest_pair(Qx, Qy)
dr, pair_r = _closest_pair(Rx, Ry)
# 比较横坐标中间点左右两边点集内的最小距离
d = min(dl, dr)
min_pair = pair_l if dl < dr else pair_r
#找到横坐标中间点左右d的条带,且是已经按照纵坐标排好序的,可以节省时间复杂度不需要在递归函数里排序
strip = [p for p in py if abs(p[0]-midpoint) < d]
for i, p in enumerate(strip):
#根据鸽笼原理,纵向为2d,横向为d的区域内最多有6个点到p的距离<d
for j in range(i+1, min(i+8, len(strip))):
dist = distance(p, strip[j])
if dist < d:
d = dist
min_pair = (p, strip[j])
return d, min_pair
# 按照纵坐标排序
py = sorted(points, key=lambda point:point[1])
return _closest_pair(points, py)
import sys
n = int(sys.stdin.readline.strip())
points = []
for _ in range(n):
points.append(tuple(map(int, sys.stdin.readline().strip().split())))
#points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(points)[0])
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Dangerous Syscalls
Test #1:
score: 0
Dangerous Syscalls
input:
2933 19320 28055 2053 27470 14635 1378 27582 9822 28729 107 22351 3093 17670 379 23901 4686 27182 12261 19443 8467 24208 20283 10763 10584 25953 28380 28290 27394 19572 14769 4024 12401 23295 3267 26949 176 13416 4517 23856 15413 26260 18957 18275 24409 999 3873 28202 14686 25446 2822 24009 8949 114...
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%