사각형과 도형
시간 제한2초메모리 제한128 MB
직사각형 좌표들이 서로 겹치지 않는 상태에서 주어진 도형의 내부를 정확히 채우도록 사각형들을 선택하는 문제입니다.
문제
2차원 평면에 n개의 점으로 정의된 도형과 m개의 축에 평행한 사각형이 있다. 도형의 점들은 주어진 순서대로 이어지며, 마지막 점은 첫 번째 점과 다시 이어진다.
서로 다른 두 사각형은 면적이 양수인 부분을 공유하지 않는다. 주어진 사각형들 중 일부를 선택해 도형을 덮으려고 한다. 선택한 사각형은 도형의 바깥으로 벗어나면 안 되며, 도형의 내부에는 선택한 사각형으로 덮이지 않은 부분이 남아 있으면 안 된다.
입력
첫째 줄에 두 자연수 n, m이 주어진다 (1 <= n <= 1,000, 1 <= m <= 10,000).
다음 n개의 줄에는 도형을 이루는 점의 좌표가 순서대로 주어진다.
다음 m개의 줄에는 각 사각형의 대각선으로 마주 보는 두 꼭짓점의 x, y좌표를 나타내는 네 정수가 주어진다.
출력
첫째 줄에 선택한 사각형의 개수 C를 출력한다. 다음 C개의 줄에는 선택한 사각형의 번호를 오름차순으로 한 줄에 하나씩 출력한다.
도형을 덮을 수 없다면 C = 0을 출력한다.