100653: [AtCoder]ABC065 D - Built?

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

Description

Score : $500$ points

Problem Statement

There are $N$ towns on a plane. The $i$-th town is located at the coordinates $(x_i,y_i)$. There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates $(a,b)$ and $(c,d)$ for a cost of $min(|a-c|,|b-d|)$ yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

  • $2 ≤ N ≤ 10^5$
  • $0 ≤ x_i,y_i ≤ 10^9$
  • All input values are integers.

Input

Input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_N$ $y_N$

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns $1$ and $2$, and another between Towns $2$ and $3$. The total cost is $2+1=3$ yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8

Input

题意翻译

## 题目描述 平面上有 $N$ 个城市。第 $i$ 个城市的坐标为 $(x_i,y_i)$ 。同一个坐标上可能有多个城市。在坐标为 $(a,b)$ 的城市和坐标为 $(c,d)$ 的城市间建造一条道路需要 $min(|a-c|,|b-d|)$ 円。只能在城市与城市间建造道路。 要使任意两个城市之间有直接或间接道路相连，最少需要多少円？ ## 数据范围 - $2 \leq N \leq 10^5$ - $0 \leq x_i,y_i \leq 10^9$ - 输入全为整数 ## 输入 输入按以下形式： $$ N $$ $$ x_1 \space y_1 $$ $$ x_2 \space y_2 $$ $$ : $$ $$ x_N \space y_N $$ ## 输出 请输出使任意两城市间有直接或间接道路连接所需最少钱数。 ## 样例1解释 在城市 $1$ 与城市 $2$ 间建造一条道路，在城市 $2$ 与城市 $3$ 间建造一条道路，花费 $2+1=3$ 円。 感谢@ミク 提供的翻译

Source/Category

加入题单

算法标签：