首页 > 试题广场 >

小红的星屑共鸣

[编程题]小红的星屑共鸣
  • 热度指数：450 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红是一位热衷于探索宇宙奥秘的星际旅行者。最近，她在银河系的边缘发现了一片古老的星云，这里漂浮着许多蕴含神秘能量的“星屑”。

小红通过她的飞船雷达扫描了这片区域，将每一颗星屑的位置都映射到了一个二维平面坐标系中。根据古老的传说，当两颗星屑的距离越近，它们之间产生的“共鸣波动”就越强烈。为了寻找能量最纯净的共鸣源，小红需要找出这片区域中距离最近的两颗星屑。

为了避免处理浮点数带来的精度误差，飞船的主控电脑（也就是你）被要求计算这两颗星屑之间欧几里得距离的平方。

形式化地讲，给定平面上 n 个点的坐标，你需要找到两个点 (x_i, y_i) 和 (x_j, y_j)（其中 i \neq j），使得它们的距离平方 D = (x_i - x_j)^2 + (y_i - y_j)^2 最小，并输出这个最小值。

输入描述:
第一行包含一个整数 n，表示星屑的数量。

接下来的 n 行，每行包含两个整数 x 和 y，表示一颗星屑在平面上的坐标。

 2 \leqq n \leqq 100,000
 -100,000 \leqq x, y \leqq 100,000


输出描述:
输出一个整数，表示所有星屑对中，最小的距离平方值。
示例1

输入

5
0 0
0 5
3 4
3 5
3 6

输出

1

说明

在样例中，最近的一对星屑坐标分别为 (3, 4) 和 (3, 5)。
它们之间的距离平方计算如下：
(3 - 3)^2 + (5 - 4)^2 = 0^2 + 1^2 = 1
没有其他点对的距离平方小于 1。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 6浏览

热门推荐

相关试题

小红的星屑共鸣

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号