71 - ZOJ Monthly, October 2008 - Robots
Wyest is fond of the game Unix Robots. It is played on a two-dimensional rectangular board. The objective of the game is to escape from a number of robots, which have been programmed with only a single objective: to kill you.
The player character and the robots start at randomly selected grids in the board. Every time the player character moves a square in any direction (horizontally, vertically, or diagonally), so does each robot, in whichever direction is the shortest way. That is, if a robot has two optimal approaches, it will first make |xrobot - xman| and |yrobot - yman| both smaller (move diagonally). (In fact there're robots moving two squares in some sets of Unix Robots, but now we're not considering them.) If the player character collides with a robot, he dies and the game ends. However, the robots are also fatal to each other - when two robots collide, they both die, leaving behind a junkheap. These junkheaps are also fatal to robots.
You can also transport into a grid in cases where moving is otherwise impossible. There're two kinds of transports, one is safe teleport, which has a limit of using, and the other is random. if you have no more safe ones, you'll have to be transported into a randomly selected location, maybe right into the path of a robot.
Generally, the player will gain one safe teleport moving onto the next level, no doubt it's too few. So the Wait button is introduced to you. If you press it, you will no longer be able to move until either all of the robots (which still move towards you) are gone, or you are killed. If you survive finally, each robot will earn you one extra safe teleports to use in future.
Now Wyest is playing the game again, and is asking you to do her a little favor. Given the situation on the board, you only need to tell her whether she can press the Wait button now.
There're multiple test cases. In each test case, the first line contains two integers x and y, coordinates of the grid where the player character is. The second line of a case is an integer n, indicating the number of robots, and n lines follow, each contains two integers xi and yi, coordinates of the grid where roboti is. Then a single line containing an integer m, indicating the number of junkheaps of previous collisions on the board, and m lines follow, each contains two integers xj and yj, coordinates of the grid where junkheapj is.
A single line for each case telling whether Wyest can Wait in the current situation, either "YES" or "NO".
0 0 2 3 1 3 -1 0 0 0 1 2 0 1 3 0
Author: WANG, Yuting