IITKWPCL - Find Distances In A Plane
Feluda loves reading city maps a lot. Now he has got a map of a city where each house is denoted with its x and y coordinate. As he is interested in estimating how good is arrangement of city, Should he would ask you these two questions.
1. What is minimum distance between any two houses ?
2. What is maximum distance between any two houses ?
Now given n points in a plane, You have to answer these two questions? As Feluda is scared by precision of decimal number representation in computers, you should tell Feluda the square of these distances.
First line will contain n : no of houses. (n >= 2 && n <= 10^5)
Then next n lines where each line will contain x and y coordinate of house seperated by a single space. (-10^9 <= x , y <= 10^9).
Output one line containing squares of minimum and maximum distance respectively seperated by single space.
10 0 0 5 1 9 2 12 3 14 4 15 5 16 7 17 10 18 14 19 19Output:2 722
Even O(N(LogN)^2) is failing??
n >= 2 as expected (confirmed with assertions).
Last edit: 2013-08-20 20:59:36