직사각형 색칠하기

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

요약
N개의 직사각형 중 정확히 K개를 골라, 겹치는 부분은 더 큰 번호가 보이는 규칙 아래 보이는 합집합 면적을 최대화하고 동점이면 사전순으로 가장 작은 번호 조합을 구합니다.
난이도

어려움10점 중 9점

유형
기하, 동적 계획법, 조합론, 그리디
정답자
아직 제출이 없습니다

문제

2차원 좌표 평면에 변이 좌표축과 평행한 직사각형 N개가 있습니다. 직사각형에는 1부터 N까지 번호가 붙어 있습니다. i번 직사각형의 왼쪽 아래 꼭짓점은 (x_i,1, y_i,1), 오른쪽 위 꼭짓점은 (x_i,2, y_i,2)입니다.

이 중 정확히 K개의 직사각형을 골라 색칠합니다. 어떤 영역을 하나 이상의 직사각형이 덮고 있다면, 그 영역에서는 덮고 있는 직사각형 중 번호가 가장 큰 직사각형만 보입니다. 색칠된 영역의 넓이는 선택한 직사각형들 중 실제로 보이는 부분의 넓이 합입니다. 이 넓이가 최대가 되도록 직사각형을 선택하세요.

입력

첫째 줄에 두 정수 N, K가 주어집니다.

둘째 줄부터 N개의 줄에 각 직사각형을 나타내는 네 정수 x_i,1, y_i,1, x_i,2, y_i,2가 주어집니다.

출력

색칠할 K개의 직사각형 번호를 오름차순으로 공백으로 구분해 출력합니다. 최댓값을 만드는 선택이 여러 가지라면, 사전순으로 가장 앞서는 수열을 출력합니다.

제한

  • 1 <= K <= N <= 50
  • -10000 <= x_i,1, y_i,1, x_i,2, y_i,2 <= 10000
  • x_i,1 < x_i,2
  • y_i,1 < y_i,2

예제3

  1. 예제 1

    입력
    3 2
1 1 5 3
3 2 7 4
2 5 9 7
    예상 출력
    2 3

  2. 예제 2

    입력
    7 4
1 1 5 4
2 2 4 3
4 0 6 2
7 1 9 4
1 5 4 7
6 5 9 7
2 5 8 6
    예상 출력
    1 3 4 7

  3. 예제 3

    입력
    4 3
-1 -5 1 1
2 2 5 6
-2 3 1 7
2 -4 6 -1
    예상 출력
    1 2 3