Problem E

The University of Iceland is estimating how long it takes to walk between classrooms to make sure students have enough time between classes to get around. In a prior contest we asked you to find the worst case, this will not be required again. The question now is what the best cases are. You should find the two buildings that are the closest and the two buildings that are the second closest.


The first line of the input is a single integer $3 \leq n \leq 10^5$, the number of buildings. The follow $n$ lines, each with two floating point numbers $-10^9 \leq x, y \leq 10^9$ denoting the entrance to a building at location $(x, y)$. We will assume that students move between these locations along straight lines with no regard to any obstacles that may be in their way. These numbers are given with at most $6$ digits after the decimal.


Print two lines. The first containing the distance between the closest buildings. The second containing the distance between the second closest buildings. Your answers should be correct within absolute or relative error less than $10^{-6}$.

Sample Input 1 Sample Output 1
0.0 0.0
1.0 2.0
2.0 2.0
3.0 0.0
3.0 3.0
Sample Input 2 Sample Output 2
1.0 0.0
0.0 1.0
1.0 1.0
2.0 1.0
1.0 2.0

Please log in to submit a solution to this problem

Log in