Grand Theft Auto Wheel

Time limit3sMemory limit256 MB

Summary
Given star-shaped polar polygons for a bolt hole and several wrench lugs, determine which wrenches can be inserted but cannot fully rotate inside the bolt hole.
Level

Hard9 of 10

Topics
Geometry, Simulation, Math
Solved
No attempts yet

Problem

Tommy is a wheel thief. His job used to be simple: lift a car, unscrew the wheel bolts, take the wheel, and run. But nowadays everyone uses "anti-theft" bolts.

An anti-theft bolt is designed so that it cannot be loosened with an ordinary wrench. Its head is a cylinder with a hole, and to loosen it you need a dedicated wrench: a ring with a lug shaped to fit exactly into the hole of the bolt head.

A bolt head and its matching wrench

Tommy cannot carry a wrench for every possible anti-theft bolt. Fortunately, a bolt can sometimes be loosened with a wrench that does not match it exactly.

Formally, a wrench can loosen a bolt if and only if both of the following hold:

  • the ring of the wrench can be placed onto the bolt head so that the lug of the wrench lies inside the hole of the bolt head;
  • while the bolt is held fixed, the wrench cannot make a full turn.

Cases in which a bolt can be loosened by a non-matching wrench

Both shapes -- the hole of the bolt head and the lug of the wrench -- are star-shaped polygons whose center coincides with the center of the bolt (or of the wrench). Written in polar coordinates as a sequence of pairs (ri,φi)(r_i, \varphi_i), they satisfy φi<φi+1\varphi_i < \varphi_{i+1} and φi+1−φi<180∘\varphi_{i+1} - \varphi_i < 180^\circ, so the center always lies strictly inside.

A star-shaped polygon

Determine which of Tommy's wrenches can loosen the bolt.

Input

The first line contains two integers nn and RR -- the number of wrenches and the radius of the bolt head and of the wrenches' rings (1≤n≤101 \le n \le 10, 1≤R≤10001 \le R \le 1000).

Next comes the description of the bolt head: an integer mm -- the number of vertices (3≤m≤1003 \le m \le 100) -- followed by mm integer pairs (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).

The remaining lines describe the nn wrenches in the same format.

Output

On the first line, print the number of wrenches that can loosen the bolt. On the second line, print their indices (starting from 1) in increasing order, separated by single spaces. If no wrench works, print only the first line (the number 0).

Examples6

  1. Example 1

    Input
    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
    Expected output
    2
1 3

  2. Example 2

    Input
    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
    Expected output
    2
1 4

  3. Example 3

    Input
    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
    Expected output
    1
1

  4. Example 4

    Input
    1 12
4
10 0
10 90
10 180
10 270
4
6 0
6 90
6 180
6 270
    Expected output
    0

  5. Example 5

    Input
    1 10
4
8 0
8 90
8 180
8 270
4
7 0
7 90
7 180
7 270
    Expected output
    1
1

  6. Example 6

    Input
    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
    Expected output
    2
1 2