CF475F 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$。