dlaud5379   1년 전

(지문에서 누락된 조건을 assert문으로 확인해 추가했습니다. 문제가 될 경우 삭제해 주세요.)

문제

2차원 평면에 n개의 점으로 이루어진 도형과 m개의 직사각형이 있다. 도형은 볼록하지 않을 수 있으며 x축이나 y축에 평행하지 않은 변을 가질 수 있지만, 직사각형의 모든 변은 x축이나 y축에 평행하다. 서로 다른 두 직사각형은 면적을 갖는 부분을 공유하지 않는다.

주어진 직사각형들 중 몇 개를 선택해 주어진 도형과 일치하게 만들 수 있는지 확인하는 프로그램을 작성하여라. 즉, 직사각형을 적절히 선택했을 때 주어진 도형의 바깥으로 벗어나는 직사각형이 있거나, 도형의 내부에 직사각형으로 덮이지 않은 부분이 있어서는 안 된다.

입력

첫째 줄에 n과 m이 공백으로 구분되어 주어진다. (3 ≤ n ≤ 1,000, 1 ≤ m ≤ 10,000)

둘째 줄부터 n개의 줄에 걸쳐 도형을 이루는 n개의 꼭짓점들이 차례대로 주어진다. 이 중 i번째 줄에는 도형의 i번째 꼭짓점의 좌표 xi와 yi가 공백으로 구분되어 주어진다. 도형의 모든 꼭짓점은 서로 다르며, 내각이 0도이거나 180도인 꼭짓점은 주어지지 않는다.

다음 줄부터 m개의 줄에 걸쳐 m개의 직사각형이 주어진다. 이 중 i번째 줄에는 ai, bi, ci, di가 공백으로 구분되어 주어지며, 이는 i번째 직사각형의 대각선으로 마주 보는 두 꼭짓점이 (ai, bi)와 (ci, di)라는 의미이다.

주어지는 모든 좌표는 -2×109 이상 2×109 이하의 정수이다.

출력

첫째 줄에 선택한 직사각형의 개수 C를 출력한다.

둘째 줄부터 C개의 줄에 걸쳐 선택한 직사각형의 번호를 오름차순으로 출력한다. 직사각형의 번호는 1 이상 m 이하이며, 입력으로 주어진 순서와 같다.

만약 주어진 직사각형들을 적절히 선택해 주어진 도형과 일치하게 만들 수 없을 경우, 0을 한 줄로 출력한다.

댓글을 작성하려면 로그인해야 합니다.