No.168 Ruler
タグ : / 解いたユーザー数 204
作問者 :
nmnmnmnmnmnmnm
/ テスター :
kroton
Problem Statement
There are $N$ distinct integer coordinate points $P_1$ to $P_N$ on the $XY$-plane.
A wants to connect $P_1$ to $P_N$ by joining points with straight lines.
(The order in which points are connected does not matter. It is not necessary to pass through all the points.)
To connect a pair of points, he places a ruler against them and draws one straight line in a single stroke with a pencil.
If the ruler's length is insufficient, he must not connect them by drawing the line in two or more separate strokes.
In A's town, rulers are sold in lengths that are multiples of $10cm$.
He can buy rulers such as $10cm$ or $20cm$.
For example, if he buys a $30cm$ ruler, he can draw straight lines of length at most $30cm$.
A wants to achieve his goal of connecting the points, but would rather not buy a ruler that is very long if possible.
What is the length of the shortest ruler A can buy to achieve his goal of connecting the points?
Input
$N$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$
$N$ is the number of points. $2\le N \le 1000=10^3$
$X_i$,$Y_i$ are the coordinates of the $i$-th point $P_i$. $0\le X_i,Y_i \le 1000000000=10^9$
If $i \neq j $, then $(X_i,Y_i) \neq (X_j,Y_j)$
One unit of length in the coordinates is $1cm$.
Output
Output on one line the length of the shortest ruler A needs to buy.
Do not forget the newline at the end.
Sample
Sample 1
Input
3 0 0 10 10 15 14
Output
20
There are 3 points on the $XY$-plane.
$P_1$ is $(0,0)$, $P_2$ is $(10,10)$, and $P_3$ is $(15,14)$.
We want to connect points with lines so that $P_1$ is connected to $P_3$.
Here, the distance from $P_1$ to $P_2$ is $14.1421\cdots cm$, and the distance from $P_2$ to $P_3$ is $6.4031\cdots cm$.
Therefore, a $20cm$ ruler is needed to draw the line from $P_1$ to $P_2$.
The line from $P_2$ to $P_3$ can also be drawn with the $20cm$ ruler.
Thus, $P_1$ can be connected to $P_3$ with a $20cm$ ruler.
Sample 2
Input
3 0 0 10 10 5 5
Output
10
There are 3 points on the $XY$-plane.
$P_1$ is $(0,0)$, $P_2$ is $(10,10)$, and $P_3$ is $(5,5)$.
We want to connect points so that $P_1$ is connected to $P_3$ with lines.
The length from $P_1$ to $P_3$ is $7.0710\cdots cm$, so a $10cm$ ruler is enough to connect them with a line.
In this sample, the point $P_2$ does not necessarily need to be connected by a line.
Sample 3
Input
2 0 0 1000000000 1
Output
1000000010
Be careful about precision errors of the double type.
Sample 4
Input
10 22332 32623 1203 95262 31305 81403 22442 55471 89784 78507 63397 32214 67779 12590 991 97116 79915 80450 6595 94117
Output
27790
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。