#1001 최소, 최대 정사각형 찾기

166  1 s   128 MB  

Description

$N$개의 점이 주어졌을 때, 임의로 $4$개의 점을 이어서 정사각형을 만들려고 한다. 가능한 경우 중 가장 작은 정사각형의 변의 길이와 가장 큰 정사각형의 변의 길이를 찾는 프로그램을 작성한다.

만들 수 있는 정사각형은 반드시 $x$축과 $y$축에 평행해야 한다.

Input

첫 행에는 테스트 케이스의 수 $T$ $( 1 \leq T \leq 20 )$가 주어진다.

각 테스트 케이스의 첫번째 줄에는 점의 개수 $N$ $( 4 \leq N \leq 50 )$이 입력된다. 그 다음의 $N$개의 줄에는 점의 $x$좌표와 $y$좌표가 입력된다. 좌표는 반드시 정수 좌표로 입력되며, $-10^4$ 이상 $10^4$ 이하의 범위 안으로 입력이 된다고 가정한다. 

같은 위치에 두개의 점이 존재하는 경우는 없으며, 또 정사각형을 만들 수 있는 조합은 반드시 하나 이상 존재한다.

Output

테스트 케이스 하나당 한 줄에 만들 수 있는 정사각형의 최소 길이와 최대 길이를 공백을 사이에 두고 출력한다. 테스트 케이스에서 정사각형을 하나도 만들 수 없는 경우는 존재하지 않는다고 가정한다.

Sample Input

Sample Output

2
4
0 0
2 2
2 0
0 2
10
0 0
2 2
2 0
0 2
-10 -10
7 7
10 10
-10 10
10 -10
5 8
2 2
2 20

Source

정현환 (아주대학교)