Queries With Points

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let's solve a realistic problem now! You are given the world map where each country is a polygon on the 2D plane. You may already now that the Global Positioning System can help you to know your current coordinate. So how can you determine which country are you in? That what you need to figure out in this problem. We will give you more detail about input and output description now
There are N countries which are numbered from 1 to N. Each country is represented by a single simple polygon on the 2D plane. Simple polygon means the boundary of the polygon does not cross itself. You should not confuse simple polygon with convex polygon. There are no two countries share a common point.
You have to answer Q queries, each query requires you to find the polygon that contain a specific point. Note that a point on the boundary of the polygon is considered to be inside the polygon. This problem is set in interactive mode that means you need to answer each query right after you read it.
Input
 The first line of input contains a single integer N which is the number of countries
 The ith line in the next N lines describes the boundary of the ith country. It starts with an integer k and then k pairs of integers (where each pair represent a vextex in 2D) follow. A country's boundary can be drawn by connecting these pairs of vertices in the same order as supplied using straight lines (Finally connect last vertex with first vertex).
 The next line contains a single integer Q which is the number of queries.
 Each line in the next Q lines contains a pair of integer which is the coordinate in the query.
Output
For each query you print out one number which is the index of the country that contains the query point. Print out 1 if there is no country contains that point.
Attention: the program should clear the output buffer after printing each line. It can be done using fflush(stdout) command or by setting the proper type of buffering at the beginning of the execution  setlinebuf(stdout).
Constraints
 1 ≤ N ≤ 100,000
 3 ≤ K ≤ 300,000
 Sum of all values of K is less than 300,000
 1 ≤ Q ≤ 100,000
 All coordinates are nonnegative integer which are not exceed 10^{9}
Example
Input: 2 4 1 4 1 7 7 7 7 4 3 1 1 5 3 7 1 3 2 3 3 6 6 2 Output: 1 1 2
Explanation
Example case 1. The test case is represented in figure below.
The first country is the rectangle ABCD and the second country is a triangle EFG. Notice that the point J at coordinate (6, 2) is considered to be inside the second country when it is on the boundary of this country
Author:  tuananh93 
Editorial  http://discuss.codechef.com/problems/QPOINT 
Tags  datastructure, geometry, hard, interactive, nov13, tuananh93 
Date Added:  26092013 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions