问题4267--RPG的地图

4267: RPG的地图

[命题人 : ]
时间限制 : 3.000 sec  内存限制 : 128 MB

题目描述

lyf有天晚上做梦,梦见自己去游戏公司实习了。那里正准备做一款RPG游戏,lyf在做游戏地图时遇到这样的一个问题:
游戏里有一个不规则的地图,可能是凹多边形,也可能是凸多边形,已经处理出了这个多边形轮廓的坐标,并且把这些坐标以逆时针的顺序给出。比如说下面这个图形:

那么我们会以(4,0),(3,3),(0,3),(-2,0),(0,-3),(3,-3)的顺序把坐标给出。
现在lyf要完成的任务是要完成m次询问,每次给出一对坐标(x, y),要判断出(x, y)是否在给出的多边形内。
请帮lyf解决这个问题吧。

输入

有多组数据(组数<=10)。
每组数据输入形如:
n m
x1 y1
x2 y2
....
xn yn
askX1 askY1
askX2 askY2
...
askXm askYm
n(3 <= n <= 100000)表示多边形轮廓上的点个数,它们以逆时针的顺序给出, 给出的点保证能构成多边形。
m (1 <= m <= 200000) 表示询问次数, 询问(askXi, askYi)是否在多边形内,注意如果在多边形的边上,也认为在多边形内部。
-1000<=xi, yi, askXi, askYi<=1000, 它们都为整数。

输出

每组输出形如:
ans1
ans2
...
ansm
ansi:表示如果第i次询问的坐标在多边形内,输出“Yes”, 否则输出“No”。

样例输入 Copy

6 3
4 0
3 3
0 3
-2 0
0 -3
3 -3
0 0
4 1
-1 2

样例输出 Copy

Yes
No
No

来源/分类