IITKWPCL - Find Distances In A Plane

no tags 

    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. 


0 0
5 1
9 2
12 3
14 4
15 5
16 7
17 10
18 14
19 19
2 722

hide comments
Achint: 2013-09-03 04:59:23

Even O(N(LogN)^2) is failing??

Miguel Oliveira: 2013-08-21 20:00:39

n >= 2 as expected (confirmed with assertions).

Alien: 2013-08-21 20:00:39

Last edit: 2013-08-20 20:59:36

Added by:praveen123
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge