2614. 组网计划

单点时限: 2.0 sec

内存限制: 256 MB

Pollux 有 N 台电脑,现在他想建立一个网络,使得这 N 台电脑之间能互相通信。他的要求不高,只需要建立一个简单的网络就行,假如 A 电脑和 B 电脑能互相通信,那么所有能与 A 电脑通信的电脑,也能与 B 电脑通信,反之亦然。如果要在 A,B 两台电脑之间连接网线,那么所需要的代价就是他们之间的距离大小 (定义距离 d=|Ax-Bx|+|Ay-By|)。Pollux 迫切的想知道他要建立这个网络的最小花费,而且以防万一,他还想知道是否有另一种方案,使得和最优方案的花费相同。

当两个方案所连接的所有网线中,如果至少有一条边不一样则他们属于是两种不同的方案 .

输入格式

本题有多组测试数据。

每组数据第一行输入一个整数 N(1<=N<=100).

接下去 N 行,每行两个整数 X,Y(0<=X,Y<=100). 第 i+1 行表示第 i 台电脑的平面坐标 .

输出格式

对每组测试数据输出两行。第一行输出一个整数,表示最小花费。

如果存在另一种方案使得其花费和最优方案的花费相同,则第二行输出 Yes, 否则第二行输出 No.

样例

Input
11
10 52
14 82
28 24
33 94
59 4
17 73
53 85
31 100
74 74
12 72
38 34
3
0 0
1 1
2 2
Output
257
Yes
4
No

163 人解决,201 人已尝试。

256 份提交通过,共有 802 份提交。

2.9 EMB 奖励。

创建: 15 年,7 月前.

修改: 7 年,4 月前.

最后提交: 6 月,2 周前.

来源: 华东师范大学2009校赛

题目标签