Moocast

题目描述

农夫约翰的 $N$ 头奶牛（$1 \leq N \leq 1000$）想要组织一个紧急的“moo-cast”系统，用于在它们之间广播重要消息。 与其在远距离上互相哞叫，奶牛们决定为自己配备对讲机，每头奶牛一台。这些对讲机的传输半径有限，但奶牛可以沿着由多次中继组成的路径相互转发消息，因此并不需要每头奶牛都能直接向其他每一头奶牛发送。

奶牛们需要决定在对讲机上花多少钱。如果它们花费 $X，那么每头奶牛都会得到一台最远可传输距离为 $\sqrt{X}$ 的对讲机。也就是说，两头奶牛之间的距离平方必须不超过 $X$，它们才能通信。

请帮助奶牛确定满足以下条件的最小整数 $X$：从任意一头奶牛发起的广播，最终都能够到达其他所有奶牛。

输入格式

第一行输入为 $N$。 接下来 $N$ 行每行包含一头奶牛的 $x$ 和 $y$ 坐标。 这两个坐标都是 $0 \ldots 25,000$ 范围内的整数。

输出格式

输出一行，包含整数 $X$，表示奶牛在对讲机上必须花费的最小金额。

4
1 3
5 4
7 2
6 1

17

提示

题目贡献者：Richard Peng

标签: USACO|2016|Gold

来源

USACO|2016|Gold