#PU669. USACO 2016 December Contest, Gold — Problem 1. Moocast

    ID: 1237 传统题 文件IO:moocast 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec16来源:usaco.orgscoring:equal_test_cases数学

USACO 2016 December Contest, Gold — Problem 1. Moocast

USACO 2016 December Contest, Gold — Problem 1. Moocast

题目描述

Farmer John's NN cows (1≤N≤10001 \leq N \leq 1000) want to organize an emergency "moo-cast" system for broadcasting important messages among themselves. Instead of mooing at each-other over long distances, the cows decide to equip themselves with walkie-talkies, one for each cow. These walkie-talkies each have a limited transmission radius, but cows can relay messages to one-another along a path consisting of several hops, so it is not necessary for every cow to be able to transmit directly to every other cow. The cows need to decide how much money to spend on their walkie-talkies. If they spend $X, they will each get a walkie-talkie capable of transmitting up to a distance of X\sqrt{X}. That is, the squared distance between two cows must be at most XX for them to be able to communicate. Please help the cows determine the minimum integer value of XX such that a broadcast from any cow will ultimately be able to reach every other cow.

输入格式

The first line of input contains NN. The next NN lines each contain the xx and yy coordinates of a single cow. These are both integers in the range 0…25,0000 \ldots 25,000.

输出格式

Write a single line of output containing the integer XX giving the minimum amount the cows must spend on walkie-talkies.

数据范围

(见题面原文)

样例

样例 1

4
1 3
5 4
7 2
6 1
17
Problem credits: Richard Peng