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.

Input

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

Output one line containing squares of minimum and maximum distance respectively seperated by single space. 

Example

Input:
10
0 0
5 1
9 2
12 3
14 4
15 5
16 7
17 10
18 14
19 19
Output:
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
Date:2013-08-06
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge