Chef and Polygons

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
Chef is not very good with geometric problems, and he, therefore, asks you to solve one of them. He has N red points and M black points, and Q queries on them. In each query, he will give you a subset of red points, you have to find out number of black points lying strictly inside the convex polygon formed by using the given subset as vertices.
Input
The first line of input contains two integers — N and M — denoting the number of red and black points, respectively. The next N lines contain two spaceseparated integers each denoting the coordinates of red points, with the i^{th} line describing the i^{th} point. Analogously, the next M lines contain two spaceseparated integers each denoting the coordinates of the black points. The next line contain one integer Q denoting the number of polygons. Each of the next Q lines contains a polygon in the form k i_{1} i_{2} … i_{k}. Here, k is the number of vertices of the polygon, and i_{1}, i_{2}, …, i_{k} are the indices of red points which form the polygon, in a clockwise order.
Output
For each query, output a new line containing the answer to it.
Constraints
 3 ≤ N ≤ 10^{2}
 1 ≤ M ≤ 3 × 10^{3}
 1 ≤ Q ≤ 10^{6}
 3 ≤ k ≤ N
 Sum of k over all queries is at most 10^{6}
 Absolute value of a coordinate of any point is at most 10^{4}
 No three points lie on the same line
Example
Input: 4 2 0 0 2 0 2 3 0 3 1 1 1 2 3 4 4 3 2 1 3 1 4 2 3 1 3 2 Output: 2 1 1 Input: 9 9 62 73 66 27 14 85 82 19 42 42 38 85 38 44 11 55 46 9 44 6 98 13 3 97 61 34 70 17 11 13 95 25 52 60 12 3 8 4 9 6 3 1 5 2 5 7 1 4 4 2 6 3 4 5 5 6 1 4 8 5 2 5 7 1 8 4 2 6 3 4 3 2 6 8 5 9 5 7 4 8 Output: 0 1 1 3 2 1 0 3
Subtasks
 Subtask 1: N = 3. Points  10
 Subtask 2: N, M ≤ 100. Points  20
 Subtask 3: Sum of k over all queries not be greater than 10^{5}, M ≤ 1000 Points  30
 Subtask 4: Original constraints. Points  40
Explanation
Test #1:
Polygon 1: (0, 0)(0, 3)(2, 3)(2, 0), two black points inside it: (1, 1), (1, 2).
Polygon 2: (0, 0)(0, 3)(2, 0), contains one black point inside: (1, 1).
Polygon 3: (0, 0)(2, 3)(2, 0), encloses one black point: (1, 1).
Author:  mgch 
Editorial  http://discuss.codechef.com/problems/CHEFPOLY 
Tags  geometry, ltime33, medium, mgch 
Date Added:  6022016 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 