| 2016 CodeCraft IIIT Hyderabad Replay |
|---|
| Finished |
In the magical world of felicity, there is a merry go round. This merry go round is in the shape of a convex polygon. The polygon has N points each of which is defined by x and y coordinates. Felicity celebrates a lot of magical festivals, in which any one side of the polygon acts as a magical base, i.e, it lies on the x-axis. This side is denoted by two vertices, pl and pr. When the side acts as a magical base, pl coincides with the origin and pr lies somewhere else to the right of the origin on the magical base. Unfortunately, there is an infinitely long vertical magical wand, perpendicular to the magical base, that lies at k distance from the origin on the magical base. It is ensured that k > x', where x' is maximum x-coordinate of any polygon vertex. Now this wand falls in counter-clockwise direction till it hits the merry go round.
When the wand hits the merry go round, it generates a flash at the point(s) of collision. Given Q festivals where each is defined by a base, pl and pr, and by a k, can you tell what the flash points are?
The first line contains N(3 ≤ N ≤ 105) and Q(1 ≤ Q ≤ 105), the number of points and number of festivals.
The first N lines are the points of the merry go round in counter-clockwise order and each of the lines has two integers xi and yi( - 109 ≤ xi, yi ≤ 109). Points are indexed from 0 to N - 1 in the order of input.
This is followed by Q lines where each line has two integers 
and k(
and 1 ≤ k ≤ 109). Here denotes pl of an edge and pr of that edge is 
.
Output for each query is the indices of the points that lit up. If the wand collides with only a point, output the index of that point. Else, if it collides with an edge, output the indices of the two vertices where the second vertex lies counter clockwise ahead of the first vertex.
4 1
0 0
1 0
1 1
0 1
0 2
2
