logo AlgoBeat OnlineJudge
登录 注册

#102177. [BZOJ 2177] 曼哈顿最小生成树

内存限制:259 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

平面坐标系 内,给定 个顶点 。对于顶点 之间的距离 定义为

你的任务就是求出这 个顶点的最小生成树。

输入格式

第一行一个正整数 ,表示定点个数。

接下来 行每行两个正整数 ,描述一个顶点。

输出格式

只有一行,为最小生成树的边的距离和。

样例输入

4
1 0
0 1
0 -1
-1 0

样例输出

6

数据范围与提示

对于 的数据,