| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 55 | 18 | 8 | 47.059% |
2차원 평면에 n(1 ≤ n ≤ 1,000)개의 점으로 이루어진 도형과 m(1 ≤ m ≤ 10,000)개의 사각형이 있다. 서로 다른 두 사각형은 면적을 갖는 부분을 공유하지 않는다. 이때, 주어진 사각형들 중 몇 개를 선택하면 도형을 덮을 수 있다. 도형을 덮을 때에는, 도형의 바깥으로 벗어나는 사각형을 사용할 수 없으며, 도형의 내부에 사각형으로 덮이지 않은 부분이 있어서는 안 된다.
첫째 줄에 두 자연수 n, m이 주어진다. 다음 n개의 줄에는 차례로 도형의 점들이 주어진다. 다음 m개의 줄에는 네 정수로 각 사각형의 대각선으로 마주 보는 두 꼭짓점의 x, y좌표가 주어진다.
첫째 줄에 선택한 사각형의 개수 C를 출력한다. 다음 C개의 줄에는 선택한 사각형의 번호를 오름차순으로 출력한다. 만약 덮을 수 없다면 C = 0을 출력한다.
4 3 0 0 0 2 2 2 2 0 1 0 0 2 1 0 2 2 10 9 9 10
2 1 2