3036: 翘课
内存限制:512 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:0
解决:
题目描述
小W极度厌恶学习,所以他经常翘课。新的学期他进入了新的校区,现在他想研究一下新校区的布局,以便他找到合适的翘课地点。
现在你的手上有新校区的布局图,布局图可以看做一个二维平面,其中每个教学楼都是二维平面上的一个简单多边形。
小W现在找出了Q个位置,他向你询问这Q个位置,分别是在哪个教学楼的范围中,或是在校园的空地上。
更具体地,现在平面上有n个教学楼,教学楼从1开始编号,每个教学楼可以用一个简单多边形表示,这意味着这个多边形的边只会在多边形的端点处相交。注意,简单多边形不意味着它是凸多边形。
显然教学楼不会建到一起去,所以所有的多边形互不相交,也就是说没有任何一个点同时在两个多边形的边界或者内部。
你现在需要回答小W的Q次询问,每次询问一个点是在哪个教学楼内,也就是它在哪个多边形内,一个点在多边形的边界上也算作在多边形内。
本来小W要求你按顺序答完当前询问才能开始下个询问,但是看着可怜的你,他决定降低难度,将询问全部给你,你能回答他吗?
输入
第一行一个正整数n,表示教学楼数目。
接下来n行,第i行用一个简单多边形描述第i个教学楼。
一开始一个整数K,表示这个多边形端点数目。接下来K对整数(x, y)表示这些点在二维平面上的坐标。保证顺次用线段连接第 i 个和第 i+1(1 ≤ i < K)个点,最后连接第1个点和第K个点,能得到这个多边形的边界。但不保证方向,也就是顺逆时针都有可能。
接下来一行一个整数Q,表示询问个数。
接下来Q行一对整数(x, y),表示询问的点在二维平面上的坐标。
输出
对于每组询问输出一个数字,表示包含询问点的教学楼编号。若询问点不在任何一个教学楼内,输出 -1.
样例输入 复制
2
4 1 4 1 7 7 7 7 4
3 1 1 5 3 7 1
3
2 3
3 6
6 2
样例输出 复制
-1
1
2