최소, 최대 정사각형 찾기 2
문제 정보
문제
N개의 점이 주어졌을 때, 임의로 4개의 점을 이어서 정사각형을 만들려고 한다. 가능한 경우 중 가장 작은 정사각형의 변의 길이와 가장 큰 정사각형의 변의 길이를 찾는 프로그램을 작성한다.
만들 수 있는 정사각형은 반드시 x-축과 y-축에 평행해야 한다.
입력
첫 행에는 테스트 케이스의 수 T ( 1 <= T <= 20 )가 주어진다.
각 테스트 케이스의 첫번째 줄에는 점의 개수 N ( 4 <= n <= 20,000 )이 입력된다.
그 다음의 N개의 줄에는 점의 x-좌표와 y-좌표가 입력된다. 좌표는 반드시 정수 좌표로 입력되며, -106 이상 106 이하의 범위 안으로 입력이 된다고 가정한다. 같은 위치에 두개의 점이 존재하는 경우는 없으며, 또 정사각형을 만들 수 있는 조합은 반드시 하나 이상 존재한다.
출력
테스트 케이스 하나당 한 줄에 만들 수 있는 정사각형의 최소 길이와 최대 길이를 공백을 사이에 두고 출력한다.
테스트 케이스에서 정사각형을 하나도 만들 수 없는 경우는 존재하지 않는다고 가정한다.
예제 입력
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
노트