Problem :
You are standing at point (0 , 0). You can move to any point with integer coordinates that is exactly K units away in terms of manhattan distance from the point you are currently standing at. For eg : K = 3 , and you are standing at ( 4, -3) you can go to ( 5 , -5 ) or ( 4 , 0 ) as they both are at a manhattan distance of K (note that there are other options too).
You need to answer the minimum number of moves required to reach point (x , y) or say its impossible to reach (x , y)
Constraints :
-1e5 <= x , y <= 1e5
1 <= K <= 1e9
Sample TC : K = 3
pt = ( 1 , 3 )
output : 2
explanation : In one move you can go from (0 , 0) to (-3 , 2) Distance = |0 — (-3)| + |0 — 2| = 5 , and then from (-3, 2) you can go to (1 , 3) Distance = |-3 — 1| + |2 — 3| = 5 . So 2 moves is the minimum answer.
Firstly let's perform a transformation $$$\varphi:(x,y)\mapsto (x+y,x-y)$$$ on this space. After that, the Manhattan distance turns to Chebyshev distance.
Assuming that you're currently standing at $$$P$$$, your target is $$$Q$$$, and $$$h(P,Q)$$$ is the Chebyshev distance between $$$P$$$ and $$$Q$$$, I think there're $$$3$$$ cases:
When $$$K>h(P,Q)$$$, $$$2$$$ steps is needed. We can draw a $$$2K\times 2K$$$ rectangle whose center is $$$Q$$$, and move to it's edge by $$$1$$$ step.
When $$$K\mid h(P,Q)$$$, it's obvious that we can reduce $$$h(P,Q)$$$ exactly by $$$K$$$ each time we move, so the answer is $$$h(P,Q)/K$$$.
Otherwise, $$$\lceil h(P,Q)/K\rceil$$$ steps is needed, as we can reach the edge of the rectangle mentioned in case 1 in $$$\lceil h(P,Q)/K\rceil-1$$$ steps.
Poor at English :(
What about the Impossible cases ??
I couldn't find any solution to this TC :
K = 2
pt ( 1 , 0 )
Is there a way to generalise what kind of cases will be impossible ??
Oops, it's my mistake, sorry :( There're some $$$P$$$ that $$$\varphi^{-1}(P)$$$ is not a point with integer coordinates.