Byang and The Grid Game

Labib666 Back with a Byang!
Limits 2s, 512 MB

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 (x0x_0, y0y_0), a list of PP other distinct cells of the form (xix_i, yiy_i), and a list of KK moves of the form (dxidx_i, dyidy_i).

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. (x0x_0, y0y_0) represents the y0y_0-th column of the x0x_0-th row and this is where the game begins. If you are at the (px,py)(px, py)-th cell and you make the move #i [which is represented by (dxi,dyi)(dx_i, dy_i)], your next position will be (px+dxi,py+dyi)(px+dx_i, py+dy_i).

You can use only one of the given KK 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: PP (0P1050 \le P \le 10_5), KK (1K1031 \le K \le 10_3), x0x_0, y0y_0.

The next PP lines will contain the locations of the PP coin cells. Each of the lines will have 2 integers: xix_i, yiy_i. (109xi-10^9 \le x_i, yi109y_i \le 10^9, 1iP1 \le i \le P)

The following KK lines will contain the list of moves one can make during the game. Each of the lines will contain 2 integers: dxidx_i, dyidy_i. (109dxi-10^9 \le dx_i, dyi109dy_i \le 10^9, 1iK1 \le i \le 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 PP 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”.


Login to submit.


40% Solution Ratio
moinul.shaonEarliest, Dec '15
arefinnomiFastest, 0.0s
arefinnomiLightest, 0 B
habijabiShortest, 1062B
Toph uses cookies. By continuing you agree to our Cookie Policy.