Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Byang and The Grid Game

By Labib666 · 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 (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”.



38% Solution Ratio

moinul.shaonEarliest, Dec '15

Ayve_178Fastest, 0.5s

moinul.shaonLightest, 1.0 MB

habijabiShortest, 1062B


Login to submit

Related Contests

Back with a Byang! Ended Dec '15