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 : number of houses. (2 <= n <= 10^5)

Then next n lines where each line will contain x and y coordinate of house separated by a single space. (-10^9 <= x , y <= 10^9).

Output

Output one line containing squares of minimum and maximum distance respectively separated 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
smso: 2022-06-29 07:37:03

Have to deal with nasty 64bit overflows.

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).


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