首页 > 试题广场 >

任意点

[编程题]任意点
  • 热度指数：13 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。
请问至少需要加多少个点，使得点对之间互相可以到达。

输入描述:
第一行一个整数n表示点数（ 1 <= n <= 100)。
第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。
y轴正方向为北，x轴正方形为东。


输出描述:
输出一个整数表示最少需要加的点的数目。
示例1

输入

2
2 1
1 2

输出

1
示例2

输入

2
2 1
4 1

输出

0
算法知识视频讲解
开通博客
头像 Eihuvita.
发表于 2020-06-09 14:15:24
题意 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。 输入描述 第一行一个整数n表示点数（ 1 <= n <= 100)。 第二行n行，每 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 白给怪
发表于 2020-06-02 20:37:48
题目链接：https://ac.nowcoder.com/acm/problem/15808说到这道题，就介绍一道及其相似的题目--- 加边无向图（链接：https://ac.nowcoder.com/acm/problem/14685）任意点这道题是很明显的一道并查集的题目，用一个复杂度为O（lo 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 19_hanhan
发表于 2020-06-10 10:12:18
题目 题目描述： 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。 输入描述： 第一行一个整数n表示点数（ 1 <= n <= 100)。 第二行n行，每行两个整数x 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-06-03 23:26:35
并查集 题目描述 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。 输入描述: 第一行一个整数n表示点数（ 1 <= n <= 100)。第二行n行，每行两个整数xi, yi 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 苟且的狮子
发表于 2020-06-11 22:28:12
并查集 题意： 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。请问至少需要加多少个点，使得点对之间互相可以到达。输入描述:第一行一个整数n表示点数（ 1 <= n <= 100)。第二行n行，每行两个整数xi, yi表示坐标（ 1 &l 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Eihuvita.
发表于 2020-06-09 14:03:06
题意 在学习Operating System的过程中，Glory遇到了这样一个问题，现在有一个大小为可以容纳N个页面的内存，硬盘内的内容被分成M个页面，用1~M来标识，一开始内存里没有任何页面，接下来用户会请求Q个页面，你需要设计一个置换算法，使得缺页发生的次数最少。缺页是指用户请求某 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 夜空的弧光灯
发表于 2022-07-12 21:41:17
任意点-并查集 题目描述 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。 请问至少需要加多少个点，使得点对之间互相可以到达。 输入描述: 第一行一个整数n表示点数（ 1 <= n <= 100)。 第二行n行，每行两个整数xi, y 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 灯又烬
发表于 2020-06-02 08:13:24
题意 平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。请问至少需要加多少个点，使得点对之间互相可以到达。 题解 如果n个点之间可以相互到达，则将n个点放入一个集合。所需添加的点数就是集合数-1故：可以遍历所有点对，若彼此可达，则使用并查集将二者并到一 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 DaMing
发表于 2020-06-02 10:28:59
一个并查集的裸体对于两个点在什么情况下可以联通：横坐标相同或者纵坐标相同（在同一行或者同一列）然后求图中有几个联通块就可以了，假如有n个联通块，我需要加n-1个点能够使他们全部联通使得任两点之间可以互相到达代码 #include <map> #include <set> #i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 昵称很长很长真是太好了
发表于 2020-06-05 16:35:58
题解：跟加边的无向图其实差不多，就是看看添加几条边让其图中的边都可以相互到达，因为用的是路径压缩的算法，所以我们只需要查看一下一空有几个集合，也就是说有几个f[x]==x（根节点）就可以了。 /*Keep on going Never give up*/ #pragma GCC optimize(3 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

并查集
上传者：牛客301599号
难度：
0条回答 87浏览

热门推荐

通过挑战的用户

查看代码

相关试题

任意点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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