가장 많이 나오는 정사각형

면접 대비

시간 제한1초메모리 제한128 MB

요약
정수 격자 위의 점 30개 이하가 주어질 때, 네 점으로 만드는 축에 평행한 정사각형을 모두 세고 가장 많은 정사각형이 나오는 변의 길이를, 동률이면 가장 큰 길이를 출력한다.
난이도

보통10점 중 4점

유형
완전 탐색, 기하, 해시맵, 구현
정답자
아직 제출이 없습니다

문제

평면 위 격자점들의 집합이 주어진다. 네 꼭짓점이 모두 주어진 점 집합에 속하는 축에 평행한 정사각형(변이 수평 또는 수직이며 절대 기울어지지 않은 정사각형)을 모두 생각하자. 이러한 정사각형들 중에서 가장 많이 나타나는 변의 길이가 무엇이고, 그 변의 길이를 갖는 정사각형이 몇 개인지 구하라.

그림

예를 들어 위 그림에서는 변의 길이가 22인 정사각형이 33개, 변의 길이가 44인 정사각형이 33개 있다.

입력

첫째 줄에 테스트 케이스의 수 TT가 주어진다 (T≤50T \le 50).

이어지는 TT개의 각 줄은 하나의 테스트 케이스를 나타낸다. 각 줄은 점의 개수 kk (k≤30k \le 30)로 시작하고, 그 뒤에 kk개의 좌표 쌍(즉 정수 2k2k개)이 온다. 모든 좌표는 0≤x,y≤300 \le x, y \le 30인 정수이다.

출력

각 테스트 케이스마다 한 줄을 출력한다.

점들로 축에 평행한 정사각형을 하나 이상 만들 수 있으면 다음과 같이 출력한다.

LENGTH = L, COUNT = C

여기서 LL은 가장 많은 정사각형을 이루는 변의 길이이고, CC는 그 변의 길이를 갖는 정사각형의 개수이다. 최대 개수를 갖는 변의 길이가 여러 개라면 그중 가장 큰 변의 길이 LL을 사용한다.

점들로 축에 평행한 정사각형을 하나도 만들 수 없으면 다음을 출력한다.

No squares among the points.

예제1

  1. 예제 1

    입력
    8
    4 0 0 1 1 0 1 1 0 
    4 0 0 2 1 0 1 1 0 
    4 0 0 2 2 0 2 2 0 
    9 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
    9 0 0 0 2 0 4 2 0 2 2 2 4 4 0 4 2 4 4
    10 2 3 0 2 2 1 2 0 1 1 1 2 3 3 3 0 0 1 0 0 
    10 2 0 3 2 0 1 2 1 1 0 3 3 1 3 2 3 2 2 3 0 
    10 3 1 2 2 3 3 0 2 0 0 2 0 0 1 1 1 1 3 1 2 
    
    예상 출력
    LENGTH = 1, COUNT = 1
    No squares among the points.
    LENGTH = 2, COUNT = 1
    LENGTH = 1, COUNT = 4
    LENGTH = 2, COUNT = 4
    LENGTH = 1, COUNT = 1
    LENGTH = 1, COUNT = 1
    LENGTH = 2, COUNT = 2