There are $N$ regions which are numbered from $1$ to $N$. Each region 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 regions share a common point.
Now given $Q$ queries,I have 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.
Now ,suppose if we have $N=2$ which can be as large as $10^6$ in input.and suppose the two regions coordinates are given as follow:-
Region 1 : $4$ (show number of coordinates pair)
$(1,4),(1,7),(7,7),(7,4)$
Region 2 : $3$
$(1,1),(5,3),(7,1)$
Now ,suppose we have $3$ queries :
$(2,3),(3,6),(6,2)$
We can clearly see first one is not in any of the regions second is in first region and third is in third region.
How to solve this problem if I have large number of queries of order $10^6$ and provided that $3 ≤$ total coordinate pairs for each polygon $≤ 300,000$ and all coordinates are non-negative integer which do not exceed $10^9$.