자동차 휠 도둑

시간 제한3초메모리 제한256 MB

요약
별 모양 극좌표 다각형으로 주어진 볼트 구멍과 여러 렌치 돌기에 대해, 끼울 수는 있지만 완전히 회전은 못 하는 렌치를 모두 찾는 문제입니다.
난이도

어려움10점 중 9점

유형
기하, 시뮬레이션, 수학
정답자
아직 제출이 없습니다

문제

토미는 자동차 휠을 훔치는 도둑이다. 예전에는 일이 아주 쉬웠다. 차를 들어 올리고, 휠 볼트를 풀고, 휠을 떼어 달아나면 그만이었다. 하지만 요즘은 모두가 "도난 방지" 볼트를 사용한다.

도난 방지 볼트는 일반 렌치로는 풀 수 없도록 설계되어 있다. 볼트 머리는 구멍이 뚫린 원기둥 모양이며, 이 볼트를 풀려면 구멍 모양과 정확히 들어맞는 돌기(lug)가 달린 링 형태의 전용 렌치가 필요하다.

볼트 머리와 그에 맞는 렌치

토미는 가능한 모든 도난 방지 볼트에 맞는 렌치를 다 가지고 다닐 수는 없다. 다행히도, 정확히 들어맞지 않는 렌치로도 볼트를 풀 수 있는 경우가 있다.

엄밀히 말하면, 어떤 렌치로 볼트를 풀 수 있는 것은 다음 두 조건이 모두 성립할 때, 그리고 오직 그때뿐이다.

  • 렌치의 돌기가 볼트 머리의 구멍 안에 들어가도록 렌치의 링을 볼트 머리에 끼울 수 있다.
  • 볼트를 고정한 상태에서 렌치를 완전히 한 바퀴 돌릴 수 없다.

맞지 않는 렌치로도 볼트를 풀 수 있는 경우들

볼트 머리의 구멍과 렌치의 돌기는 모두 중심이 볼트(또는 렌치)의 중심에 있는 별 모양 다각형이다. 이를 극좌표로 순서쌍 (ri,φi)(r_i, \varphi_i) 의 수열로 나타내면 φi<φi+1\varphi_i < \varphi_{i+1} 이고 φi+1−φi<180∘\varphi_{i+1} - \varphi_i < 180^\circ 를 만족하므로, 중심은 항상 다각형 내부에 놓인다.

별 모양 다각형

토미가 가진 렌치들 중 어떤 것으로 볼트를 풀 수 있는지 판별하여라.

입력

첫 줄에 두 정수 nn 과 RR 이 주어진다. nn 은 렌치의 개수, RR 은 볼트 머리와 렌치 링의 반지름이다 (1≤n≤101 \le n \le 10, 1≤R≤10001 \le R \le 1000).

이어서 볼트 머리가 주어진다. 먼저 꼭짓점의 개수 mm (3≤m≤1003 \le m \le 100) 이 주어지고, 그다음 mm 개의 정수쌍 (ri,φi)(r_i, \varphi_i) 가 주어진다 (1≤ri<R1 \le r_i < R; 0∘≤φi<360∘0^\circ \le \varphi_i < 360^\circ; φi<φi+1\varphi_i < \varphi_{i+1}; φi+1−φi<180∘\varphi_{i+1} - \varphi_i < 180^\circ; φm−φ1>180∘\varphi_m - \varphi_1 > 180^\circ).

그 뒤로 nn 개의 렌치가 같은 형식으로 주어진다.

출력

첫 줄에 볼트를 풀 수 있는 렌치의 개수를 출력한다. 둘째 줄에는 그 렌치들의 번호(1부터 시작)를 오름차순으로 공백으로 구분하여 출력한다. 풀 수 있는 렌치가 하나도 없으면 첫 줄(0)만 출력한다.

예제6

  1. 예제 1

    입력
    3 10
4
9 0
9 90
9 180
9 270
4
8 45
8 135
8 225
8 315
4
6 45
6 135
6 225
6 315
3
7 0
7 90
6 225
    예상 출력
    2
1 3

  2. 예제 2

    입력
    4 15
4
10 0
10 90
10 180
10 270
4
9 0
9 90
9 180
9 270
4
6 0
6 90
6 180
6 270
4
12 0
12 90
12 180
12 270
4
8 45
8 135
8 225
8 315
    예상 출력
    2
1 4

  3. 예제 3

    입력
    3 12
6
10 0
10 60
10 120
10 180
10 240
10 300
6
9 0
9 60
9 120
9 180
9 240
9 300
6
7 0
7 60
7 120
7 180
7 240
7 300
6
11 0
11 60
11 120
11 180
11 240
11 300
    예상 출력
    1
1

  4. 예제 4

    입력
    1 12
4
10 0
10 90
10 180
10 270
4
6 0
6 90
6 180
6 270
    예상 출력
    0

  5. 예제 5

    입력
    1 10
4
8 0
8 90
8 180
8 270
4
7 0
7 90
7 180
7 270
    예상 출력
    1
1

  6. 예제 6

    입력
    2 12
4
10 0
10 90
10 180
10 270
4
9 10
9 100
9 190
9 280
4
9 45
9 135
9 225
9 315
    예상 출력
    2
1 2