1186번

수정 전

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

문제

  2차원 평면에 축에 평행한 직사각형 N개가 있다. 이 중 K개를 칠할 것이다.

  색칠한 면적 중 보이는 것의 최댓값을 구하는 프로그램을 작성하시오.
 

입력

  첫째 줄에 직사각형의 개수 N과 색칠해야하는 직사각형의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 직사각형의 정보가 주어진다. x1 y1 x2 y2와 같이 주어지며, (x1, y1)이 왼쪽 아래 모서리, (x2, y2)가 오른쪽 위 모서리이다. 만약 어떤 곳에 직사각형이 두 개 이상 있다면, 나중에 입력으로 들어오는 것이 보인다. 좌표는 절댓값이 10,000보다 작거나 같은 정수이고,  N은 100보다 작거나 같은 자연수, K는 N보다 작거나 같은 자연수이다.
 

출력

  첫째 줄에 보이는 색칠한 면적을 최대로 하려면, 어떤 직사각형을 칠해야 하는지 출력한다. 빈 칸으로 구분하며, 여러 가지일 경우에는 사전순으로 앞서는 것을 출력한다.

 

예제 입력

4 2 1 1 5 3 3 2 7 4 2 5 9 7

예제 출력

2 3

힌트

수정 후

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

문제

  2차원 평면에 축에 평행한 직사각형 N개가 있다. 이 중 K개를 칠할 것이다.

  색칠한 면적 중 보이는 것의 최댓값을 구하는 프로그램을 작성하시오.
 

입력

  첫째 줄에 직사각형의 개수 N과 색칠해야하는 직사각형의 개수 K가 주어진다. 둘째 줄부터 N개의 줄에 직사각형의 정보가 주어진다. x1 y1 x2 y2와 같이 주어지며, (x1, y1)이 왼쪽 아래 모서리, (x2, y2)가 오른쪽 위 모서리이다. 만약 어떤 곳에 직사각형이 두 개 이상 있다면, 나중에 입력으로 들어오는 것이 보인다. 좌표는 절댓값이 10,000보다 작거나 같은 정수이고,  N은 100보다 작거나 같은 자연수, K는 N보다 작거나 같은 자연수이다.
 

출력

  첫째 줄에 보이는 색칠한 면적을 최대로 하려면, 어떤 직사각형을 칠해야 하는지 출력한다. 빈 칸으로 구분하며, 여러 가지일 경우에는 사전순으로 앞서는 것을 출력한다.

 

예제 입력

3 2 1 1 5 3 3 2 7 4 2 5 9 7

예제 출력

2 3

힌트