302469: CF475F. Meta-universe

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Meta-universe

题意翻译

### 题目描述 平面上有无限大的网格(可以将其当做一个多重宇宙),其中有一些格子上有行星。 定义**多重宇宙**为一些行星的集合(对应了平面上的一个矩形)。 如果一个**多重宇宙**至少存在一行或一列,使得这一行或一列上没有任何行星,并且行或列两边至少各自有一颗行星(即沿着行/列划分成两个非空的多重宇宙),那么它就可以被分裂开,成为两个更小的**多重宇宙**。 定义**宇宙**为不可继续划分的**多重宇宙**。 现在给你一个**多重宇宙**上所有行星的坐标位置,你需要尽可能地将其划分,并求出最后得到的**宇宙**的数量。 ### 输入格式 第一行一个整数 $N$,表示行星的数量。 接下来 $N$ 行每行两个整数 $x_i,y_i$,表示第 $i$ 个行星的坐标。 ### 输出格式 一行一个整数,表示最多能划分成的**宇宙**数量。 ### 数据范围 $1 \leq N \leq 10^5, -10^9 \leq x_i,y_i \leq 10^9$。

题目描述

Consider infinite grid of unit cells. Some of those cells are planets. Meta-universe $ M={p_{1},p_{2},...,p_{k}} $ is a set of planets. Suppose there is an infinite row or column with following two properties: 1) it doesn't contain any planet $ p_{i} $ of meta-universe $ M $ on it; 2) there are planets of $ M $ located on both sides from this row or column. In this case we can turn the meta-universe $ M $ into two non-empty meta-universes $ M_{1} $ and $ M_{2} $ containing planets that are located on respective sides of this row or column. A meta-universe which can't be split using operation above is called a universe. We perform such operations until all meta-universes turn to universes. Given positions of the planets in the original meta-universe, find the number of universes that are result of described process. It can be proved that each universe is uniquely identified not depending from order of splitting.

输入输出格式

输入格式


Consider infinite grid of unit cells. Some of those cells are planets. Meta-universe $ M={p_{1},p_{2},...,p_{k}} $ is a set of planets. Suppose there is an infinite row or column with following two properties: 1) it doesn't contain any planet $ p_{i} $ of meta-universe $ M $ on it; 2) there are planets of $ M $ located on both sides from this row or column. In this case we can turn the meta-universe $ M $ into two non-empty meta-universes $ M_{1} $ and $ M_{2} $ containing planets that are located on respective sides of this row or column. A meta-universe which can't be split using operation above is called a universe. We perform such operations until all meta-universes turn to universes. Given positions of the planets in the original meta-universe, find the number of universes that are result of described process. It can be proved that each universe is uniquely identified not depending from order of splitting.

输出格式


Print the number of resulting universes.

输入输出样例

输入样例 #1

5
0 0
0 2
2 0
2 1
2 2

输出样例 #1

3

输入样例 #2

8
0 0
1 0
0 2
0 3
3 0
3 1
2 3
3 3

输出样例 #2

1

说明

The following figure describes the first test case: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF475F/09f25b4712b12f413b4de2f1fe0b272e040d2345.png)

Input

题意翻译

### 题目描述 平面上有无限大的网格(可以将其当做一个多重宇宙),其中有一些格子上有行星。 定义**多重宇宙**为一些行星的集合(对应了平面上的一个矩形)。 如果一个**多重宇宙**至少存在一行或一列,使得这一行或一列上没有任何行星,并且行或列两边至少各自有一颗行星(即沿着行/列划分成两个非空的多重宇宙),那么它就可以被分裂开,成为两个更小的**多重宇宙**。 定义**宇宙**为不可继续划分的**多重宇宙**。 现在给你一个**多重宇宙**上所有行星的坐标位置,你需要尽可能地将其划分,并求出最后得到的**宇宙**的数量。 ### 输入格式 第一行一个整数 $N$,表示行星的数量。 接下来 $N$ 行每行两个整数 $x_i,y_i$,表示第 $i$ 个行星的坐标。 ### 输出格式 一行一个整数,表示最多能划分成的**宇宙**数量。 ### 数据范围 $1 \leq N \leq 10^5, -10^9 \leq x_i,y_i \leq 10^9$。

加入题单

上一题 下一题 算法标签: