logo AlgoBeat OnlineJudge
登录 注册

#201036. 曼哈顿距离最小生成树

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

题目修改自 Library Checker,及数据生成器 / 校验器来源

请注意原题所有下标从 开始(-indexed),本题所有下标从 开始(-indexed)。


给定平面上的 个点

考虑一个有 个结点的完全图,对于 ,结点 之间有一条权值为 的边。

请求出该图的最小生成树。

输入格式

第一行输入一个整数 表示点的个数。

接下来 行,第 行输入两个整数 ,表示第 个点的坐标。

输出格式

第一行包含一个整数 表示最小生成树的边权之和。

接下来 行,第 行包含两个整数 ,表示最小生成树中的一条边。

如果有多解,你可以输出任意一种。

样例

样例输入 1

6
3 8
4 9
2 1
10 5
4 9
2 0

样例输出 1

21
5 2
6 3
1 2
3 1
4 1

数据范围与提示

对于 的数据,

对于 的数据,