최소, 최대 정사각형 찾기 2

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

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

노트

0개의 댓글이 있습니다.