Do Something
백준 1438 - 가장 작은 직사각형 [중복조합, 완전탐색] 본문
문제
현수는 어떤 좌표 평면에 점을 N개 찍었다. 신기하게도, 모든 점은 음이 아닌 정수 좌표에만 찍혔다.
현수는 직사각형을 하나 그리려고 하는데, 직사각형의 꼭짓점은 모두 정수 좌표이고, 모든 변이 X축과 Y축에 평행한 직사각형을 그리려고 한다. 또, 직사각형의 내부에 현수가 찍은 점이 적어도 N/2개가 들어있는 직사각형을 그리려고 한다. 점이 직사각형의 변 위에 놓여져 있는 것은 내부에 있는 것이 아니다.
이러한 직사각형 중에 넓이가 가장 작은 직사각형의 넓이를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N이 주어진다. N은 항상 짝수이며, 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 현수가 찍은 점의 정보가 X좌표 Y좌표 순으로 들어온다. 각각의 좌표는 10,000보다 작거나 같은 음이 아닌 정수이다. 모든 점은 중복되지 않는다.
출력
첫째 줄에 현수가 만든 직사각형 중 가장 넓이가 가장 작은 것의 넓이를 출력한다.
x혹은 y의 범위를 정해서 가능한 모든 사각형을 돌려보면 되는 문제다
x혹은 y의 좌표는 각각 최대 100개씩 나올수가 있다.
1, 2, 3, 4, 5, 6, 7이라는 좌표가 나올 수 있다고 할 때
(1, 1), (1, 2), (1, 3), (1,4).....(6, 7)....(7, 7)까지가 나올 수 있는 범위다.
해당 범위 안에 있는 점들을 구해서, 내가 범위를 준 좌표가 가능한것들을 정렬을 해서 N//2개가 안에 올 수 있으면 정답이 될 수 있다.
가능한 y좌표는 이 그림대로면 1, 6, 7, 8이다. 저 네 숫자를 가지고 중복조합을 구한다음에 (1, 1)이라는 범위를 검사한다고 치면 가능한 x좌표는 4, 5, 6이 된다.
4, 5, 6은 3개로 점 개수의 절반이 넘으니까 답이 될 수 있다.
두번쨰 예제는 y좌표가 3, 4, 5, 6, 7이 올 수 있다.
범위가 여러개가 나오는데 그중 (4, 6)을 검사한다고 치면 x좌표가 [3, 4, 4, 6, 6, 7] 이 나온다.
정렬을 한다음에 N//2개씩 검사하게 되면
[3, 4, 4, 6]
[4, 4, 6, 6]
[4, 6, 6, 7]
세가지가 나올 수 있고, 이중 사각형의 크기를 가장 작게하는 좌표가 [4, 4, 6, 6]이 된다.
첫 좌표가 가장 작고 마지막 좌표가 가장 크니까 검사할 필요 없이 첫좌표, 첫좌표 + N//2 - 1번째를 검사해주면 답이 된다.
from itertools import combinations_with_replacement
N = int(input())
P = [tuple(map(int, input().split())) for _ in range(N)] # 모든 좌표
Y, N, A = sorted(list(set(p[1] for p in P))), N//2, 1e10 # 좌표중에 y좌표만 뺴두기
for y1, y2 in list(combinations_with_replacement(Y, 2)): # y좌표로 중복조합 구하기(범위 만들기)
T = sorted([p[0] for p in P if y1 <= p[1] <= y2]) # 범위 안에 들어오는 x좌표들을 정렬해두기
for i in range(len(T) - N + 1): # 절반보다 적으면 안돔. 딱 N//2개씩만 검사해줌
A = min(A, (y2 - y1 + 2) * (T[i+N-1] - T[i] + 2)) # 정답이 될 수 있다면 최솟값을 구함
print(A)