Byang and The Grid Game
Byang has invented a game he wants to play with his soulmate Byangette during their spare time.
The rules are simple. You are given an infinite 2D grid, an initial position on the grid (x0,y0), a list of P other distinct cells of the form (xi,yi), and a list of K moves of the form (dxi,dyi).
There are P coins: one in each of the given cells (let’s call them ‘coin cells’). You have to collect all of them in the order they were given to win the game. (x0,y0) represents the y0-th column of the x0-th row and this is where the game begins. If you are at the (px,py)-th cell and you make the move #i [which is represented by (dxi,dyi)], your next position will be (px+dxi,py+dyi).
You can use only one of the given K moves to go from a coin cell (or, the first cell) to the next coin cell and you can use that move as many time as you want to reach the coin cell. You can change the move you are using once you get to that next coin cell. You can use the same move multiple times in order to reach different coin cells. (Look at the sample cases for a detailed explanation.)
Byang does not want to disappoint Byangette. So he wants to check whether Byangette can collect all the coins while conforming to all the rules mentioned above. As his dear friend and a good programmer, you are here to help him get the job done.
The first line of input will have 4 integers: P (0 <= P <= 105), K (1 <= K <= 103), x0, y0.
The next P lines will contain the locations of the P coin cells. Each of the lines will have 2 integers: xi, yi. (-109 <= xi, yi <= 109 , 1 <= i <= P)
The following K lines will contain the list of moves one can make during the game. Each of the lines will contain 2 integers: dxi, dyi. (-109 <= dxi, dyi <= 109 , 1 <= i <= K)
It is guaranteed that the starting cell and the coin cells are all distinct.
The first and only line of output will contain the word “Yes” (without the quotation marks) if you can collect all the P coins while conforming to the game rules, or “No” (without the quotation marks) otherwise.
1 2 0 0 3 3 5 4 -2 -1
You cannot get to cell (3,3) from cell (0,0) using only one of the given moves. Notice that it would have been possible if you were allowed to use multiple type of moves from the move list. Thus, the answer is “No”.
Labib666Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms. →