Last Updated: 13 Apr, 2021

Fastest Ninja

Moderate

Asked in company

Problem statement

After the pandemic ended, Alice and Bob finally got the chance to play some outdoor games. They decided to play “Fastest Ninja” along with their ‘N’ other friends. The game is as follows,

1. Bob and Alice are standing at coordinates (0, 0) and (‘X’, ‘Y’), respectively, in the X-Y plane.

2. All the other ‘N’ friends are standing at some coordinates in the X-Y plane. The starting positions of all the ‘N’ friends are given as a 2 - Dimensional array of integers ‘positions’, where ‘position[i]’ denotes the starting position of the i-th friend.

3. In one move, Bob and his ‘N’ friends can independently choose to do one of the following two things:

    1. Stay at their current position.

    2. Move to any of the four neighboring positions, i.e., for any (x, y) move to north(x, y + 1), south(x, y - 1), east(x + 1, y), or west(x - 1, y).

To win the game, Bob has to reach Alice before any of his ‘N’ friends catches him. As Bob’s friend, your task is to tell him whether he can win the game or not.

Note:

All the coordinates are integral coordinates on the X-Y plane

There can be multiple friends with the same starting position(including Alice and Bob).

Bob and his ‘N’ friends move simultaneously.

Bob loses if he reaches any coordinate(including Alice’s position) at the same time as any of his ‘N’ friends.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of other friends of Alice and Bob.

The second line of each test case contains two space-separated integers, ‘X’ and ‘Y’, where (‘X’, ‘Y’) denote Alice’s position.

The next ‘N’ lines of each test case contain two space-separated integers, ‘position[i][0]’  and ‘position[i][1]’, where (‘position[i][0]’, ‘position[i][1]’) denotes the starting position of the i-th friend.

Output Format:

For each test case, print 1 if Bob can win the game, else print 0.

The output of each test case will be printed in a separate line.

Note:

 You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
-10 ^ 7 <= X, Y <= 10 ^ 7
-10 ^ 7 <= position[i][0], position[i][1] <= 10 ^ 7

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea here is to consider all those scenarios when Bob cannot win the game. There are two possible scenarios:

When any of his ‘N’ friends reaches Alice before or at the same time as Bob. Since the friend who reaches Alice before Bob can wait at that position for Bob.
When any of his ‘N’ friends catch him before reaching Alice.

Let’s consider the 2nd scenario with a diagram,

Point A denotes the starting position of Bob, point D denotes the starting position of any of Bob’s ‘N’ friends, point C denotes the position of Alice, and point B denotes the position where Bob’s friend catches him before reaching Alice.

It is clear from the figure above that points B, D, and C form a triangle. Moreover, for his friend to catch him, AB must be equal to DB.

By the triangle inequality, DB + BC must be greater than or equal to DC, which is AB + BC must be greater than or equal to DC. Hence, AC must be greater than or equal to DC.

This means that for Bob’s friend to catch him before reaching Alice, the distance between Alice and Bob must be greater than or equal to the distance between Alice and his friend, which is the same as the 1st scenario as his friend can reach Alice before him. So we just need to check if any of Bob’s ‘N’ friends can reach Alice before him or not.

Algorithm:

Declare an integer, say ‘minMoves’ to store the minimum number of moves that Bob requires to reach Alice.
Do ‘minMoves’ = absolute(X - 0) + absolute(Y - 0), As the minimum number of moves that Bob requires to reach Alice is equal to the Manhattan distance between them.
Run a loop for ‘i’ from 0 to ‘N’ - 1.
- Declare an integer, say ‘currMoves’, to store the minimum number of moves that i-th friend requires to reach Alice.
- Do ‘currMoves’ = absolute(X - position[i][0]) + absolute(Y - position[i][1]), similarly the minimum number of moves that i-th friend requires to reach Alice is equal to the Manhattan distance between them.
- If ‘currMoves’ is less than or equal ‘minMoves’
  - Return false, as Bob cannot win the game, since his i-th friend can reach Alice before him.
Return true, as Bob can reach Alice before any of his ‘N’ friends.

Solve now