직사각형

아래 그림과 같이 평면 상에 개의 직사각형이 있다. 직사각형들의 변은 좌표축과 평행하다. 이들 직사각형은 겹쳐질 수도 있고, 일치할 수도 있으며, 다른 것의 내부에 그려질 수도 있다. 꼭지점은 음이 아닌 정수 좌표를 가지며 -좌표는 를 넘지 않고 -좌표는 를 넘지 않는다.

선분은 점 A(0,0)에서 시작하여 점 B에서 끝난다. 점 B(선분의 다른 끝점)는 다음 조건을 만족한다:

B의 좌표는 정수이다.

점 B는 선분 에 포함되거나 혹은 에 포함된다.

선분 AB 는 직사각형들과 교차할 수 있다. 단지 꼭지점에서만 교차하더라도 교차하는 것으로 가정한다. 선분 AB가 가능한 가장 많은 직사각형과 교차하도록 점 B의 위치를 찾는 프로그램을 작성하시오.

프로그램 이름은 rect.cpp, 실행 파일의 이름은 rect.exe, 프로그램 설명 파일 이름은 rect.hwp로 하고, 프로그램의 실행시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT로 한다. 입력 파일의 첫째 줄에 다음 세 정수가 주어진다: ,  그리고 . 다음 개의 줄 각각에는 직사각형의 왼쪽 아래 꼭지점의 -좌표와 오른쪽 위 꼭지점의 -좌표를 나타내는 네 정수가 주어진다. 입력되는 정수들 사이에는 빈칸이 있다.

2004 가을학기 문제해결기법	문제 #11

출력 형식

출력 파일의 이름은 OUTPUT.TXT로 한다. 출력 파일의 첫째 줄에 다음과 같이 세 정수를 출력한다. 먼저 교차하는 최대 직사각형의 개수를 출력하고 다음으로 점 B 의 -좌표를 출력한다. 인접한 정수들 사이에는 빈칸을 하나 둔다. 해가 여럿 있으면, 그 중 아무거나 하나를 출력하면 된다.

입력과 출력의 예

입력(input.txt)

22 14 8

1 8 7 11

18 10 20 12

17 1 19 7

12 2 16 3

16 7 19 9

8 4 12 11

7 4 9 6

10 5 11 6

출력(output.txt)

5 22 12

※ 다음은 가능한 다른 해이다.

5 22 11