A new term, new time tables. As usual there is quite some effort needed to get all the time tables to fit together nicely. But one thing that hasn’t always been considered when making the time tables is the distance between the various buildings. It’s not practical to have students take their first class in VR-II, next one in Askja and the last one in Háskólabíó. Since this is a frequent cause of frustration something has to be done. Thus the distance between the buildings has to be analyzed. Your job is to figure out the distance between the two buildings that are furthest away from one another. For the purposes of these calculations we will assume that the buildings can be represented by a single point, the location of the entrance. Despite tips from the geological department of this being incorrect we will still continue to assume that the Earth is flat in our calculations.


The first line of the input contains one integer $2 \leq n \leq 10^5$, the number of buildings. Next there are $n$ lines, each containing two real numbers $-10^9 \leq x, y \leq 10^9$ each giving the $x$ and $y$ coordinates of one building. These numbers will have at most $6$ digits after their decimal point.


One line containing the requested distance. The answer is accepted if its absolute or relative error from the correct answer is within $10^{-5}$.

Sample Input 1 Sample Output 1
0 0
0 0.5
Sample Input 2 Sample Output 2
0 0
0 1
1 0
1 1
Sample Input 3 Sample Output 3
0 1
1 -1
-1 -1
1 0
2 0
0 0
CPU Time limit 1 second
Memory limit 1024 MB
Languages English, Íslenska
Bergur Snorrason and Atli Fannar Franklín
Source Forritunarkeppni Háskóla Íslands 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in