首页 > 试题广场 >

牛之国

[编程题]牛之国
  • 热度指数：282 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛之国有个城市，牛牛作为牛之国国王，他希望所有牛之国的城市能够连通起来。现在他下令牛之国的所有施工队同时施工，同时已知牛之国的施工队的施工速度均为1距离单位/年，对于每个城市，城市的领导者都会向每个相邻的城市派出施工队进行修路（所有城市相邻），并且每个施工队都按照最短的路线修路，如果两个施工队碰头，那么两个城市相连。
现在给你个城市的坐标，牛牛想知道牛之国的城市最少需要多少年才能全部连通(城市A和城市B连通，当且仅当A到B有一条通路)。

输入描述:
第一行一个整数 (1 \leq n \leq 1000)，表示城市数量。
接下来行每行两个整数x_{i} (-10^8 \leq x_{i} \leq 10^8) ,y_{i} (-10^8 \leq y_{i} \leq 10^8)用空格分隔，表示城市的坐标。


输出描述:
输出仅有一个整数，表示城市相连需要的年数向上取整的结果。
例如，如果需要2.5年可以连通，请输出 3，如果如要 4 年可以连通，请输出 4。
示例1

输入

3
0 0
0 5
6 0

输出

3

说明

当(6,0)和(0,0)连在一起时，所有城市连在一起，此时需要3年。
示例2

输入

2
0 0
1 0

输出

1

说明

初始不连通，0.5年可以连通，向上取整得到 1。

备注:
python选手请使用pypy提交
算法知识视频讲解
开通博客
头像 丨阿伟丨
发表于 2025-09-12 17:30:23
题目链接 牛之国 题目描述 给定 个城市的二维坐标。所有城市之间都会同时开始修路，速度为 1 单位/年。任意两个城市之间的施工队都沿着直线路径相向而行。当两个施工队相遇时，这两个城市就连通了。 求使得所有城市构成一个连通图所需的最短时间，结果向上取整。 解题思路 这是一个关于连通性的最优化问题，可 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

计算几何 京东 图
难度：
2条回答 476浏览

热门推荐

相关试题

牛之国

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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