PROBLEM LINK:
Author: Vitalij Kozhukhivskij
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu
DIFFICULTY:
Easy
PREREQUISITES:
None at all 
PROBLEM:
- Initially the robot is at position (0, 0).
- In the beginning it goes 1 step to the East (i.e. In a single step, its x coordinate will increase by 1 unit.)
- then 2 steps to the North, (i.e. In a single step, its y coordinate will increase by 1 unit.)
- then 3 steps to the West, (i.e. In a single step, its x coordinate will decrease by 1 unit.)
- then 4 steps to the South, (i.e. In a single step, its y coordinate will decrease by 1 unit.)
- then 5 steps to the East,
- and so on.
You are given 105 queries of form (X,Y). You have to tell if robot ever visiter the coordinate (X,Y).
EXPLANATION:
Since number of queries is high, we need to solve all queries in O(1).
Let’s consider the vertical line as y-axis and other as x-axis. If we extend the path of the robot, we can clearly observe from the path that
. Robot visits all lines of form:
x=2*k+1 //k>=0; y ranges from -2*k to 2*k+2 (both inclusive)
x=-2*k //k>=1; y ranges from -2*k to 2*k (both inclusive)
y=2*k //k>=0; x ranges from -2*k to 2*k+1 (both inclusive)
y=-2*k //k>=1; x ranges from -2*k to 2*k+1 (both inclusive)
Now, it’s very trivial to find if a point (X,Y) lies on these possible lines.