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.
- 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.
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).
- 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 non-negative integer which are not exceed 109
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
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
|Tags||data-structure, geometry, hard, interactive, nov13, tuananh93|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.