Dragon Curve
Contest: ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3200

A dragon curve is a self-similar fractal curve. In this problem, it is a curve that consists of straight-line segments of the same length connected at right angles. A simple way to construct a dragon curve is as follows: take a strip of paper, fold it in half $$$n$$$ times in the same direction, then partially unfold it such that the segments are joined at right angles. This is illustrated here:

In this example, a dragon curve of order $$$3$$$ is constructed. In general, a dragon curve of a higher order will have a dragon curve of a lower order as its prefix. This allows us to define a dragon curve of infinite order, which is the limit of dragon curves of a finite order as the order approaches infinity.

Consider four dragon curves of infinite order. Each starts at the origin (the point $$$(0,0)$$$), and the length of each segment is $$$\sqrt2$$$. The first segments of the curves end at the points $$$(1,1)$$$, $$$(-1,1)$$$, $$$(-1,-1)$$$ and $$$(1,-1)$$$, respectively. The first turn of each curve is left (that is, the second segment of the first curve ends at the point $$$(0,2)$$$). In this case, every segment is a diagonal of an axis-aligned unit square with integer coordinates, and it can be proven that there is exactly one segment passing through every such square.

Given a point $$$(x,y)$$$, your task is to find on which of the four curves lies the segment passing through the square with the opposite corners at $$$(x,y)$$$ and $$$(x+1,y+1)$$$, as well as the position of that segment on that curve. The curves are numbered $$$1$$$ through $$$4$$$. Curve $$$1$$$ goes through $$$(1,1)$$$, $$$2$$$ through $$$(-1,1)$$$, $$$3$$$ through $$$(-1,-1)$$$, and $$$4$$$ through $$$(1,-1)$$$. The segments are numbered starting with $$$1$$$.

Input format:
The first line contains an integer $$$n$$$ ($$$1\le n\le2\cdot10^5$$$) — the number of test cases.

Each of the following $$$n$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$-10^9\le x,y\le10^9$$$) — the coordinates.

Output format:
For each test case, print a line containing two integers — the first is the index of the curve (an integer between $$$1$$$ and $$$4$$$, inclusive), and the second is the position on the curve (the first segment has the position $$$1$$$).

Constraints:
Time limit: 5.0 s
Memory limit: 1024.0 MB

Note:
You can use this illustration to debug your solution:

Example input:
5
0 0
-2 0
-7 -7
5 -9
9 9

Example output:
1 1
2 2
3 189
4 186
2 68

Editorial:
Problem author and developer: Evgeny Kapun
Let's consider two sets of dragon curves (each set contains four curves). We are going to call them order $$$n$$$ curves and order $$$n+1$$$ curves, although actually both of them are of infinite order. Order $$$n+1$$$ curves are the curves described in the problem statement, and order $$$n$$$ curves are the same curves rotated by $$$45^\circ$$$ counterclockwise and scaled by a factor of $$$\sqrt2$$$.
Notice that order $$$n$$$ curves can be transformed into order $$$n+1$$$ curves by replacing each segment with a pair of segments (each shorter by a factor of $$$\sqrt2$$$) connected at a right angle. The directions of the newly added turns alternate: the first turn on each curve is left, the next is right, and so on.
Let's consider $$$2\times2$$$ square with even coordinates (that is, with the corners at $$$(2x,2y)$$$ and $$$(2x+2,2y+2)$$$ for some integer $$$x,y$$$). There are two types of such squares: "vertical" squares, where the segments are connected as $$$(2x,2y)-(2x+1,2y+1)-(2x,2y+2)$$$ and $$$(2x+2,2y)-(2x+1,2y+1)-(2x+2,2y+2)$$$, and "horizontal" squares, where the segments are connected as $$$(2x,2y)-(2x+1,2y+1)-(2x+2,2y)$$$ and $$$(2x,2y+2)-(2x+1,2y+1)-(2x+2,2y+2)$$$.
Looking at the illustration in the statement, one can easily notice that the squares with $$$x+y$$$ even are vertical, and those with $$$x+y$$$ odd are horizontal. This can be proven by induction: this can be verified directly for the squares adjacent to the origin, and if it is true for some square containing order $$$n+1$$$ segments produced from some order $$$n$$$ segment, it will be also true for the squares containing the segments produced from any adjacent order $$$n$$$ segments. As all the order $$$n$$$ segments are connected to the origin, this means that the statement is valid for the entire plane.
Now, given the coordinates, it is possible to determine the type of the $$$2\times2$$$ square the segment is in, and map it to the corresponding segment on the (rotated and scaled) order $$$n$$$ curve. The illustration given in the problem statement helps very much with this step. The exact transformation is given by this Python code:
The next problem is to track the position within the segment. After the transformation given above is performed, each segment corresponds to two original segments. After the transformation is performed multiple times, each segment corresponds to a number of original segments. Unfortunately, there is no simple rule to determine the direction of the segments (specifically, which end is closer to the origin on the curve). So, a position on a segment can be defined using the following rule: measure the position starting from the end that is "more even". The "evenness" of the point $$$(x,y)$$$ can be defined as follows: if $$$x+y$$$ is odd, the evenness is $$$0$$$, otherwise, if both $$$x$$$ and $$$y$$$ are odd, the evenness is $$$1$$$, otherwise, both $$$x$$$ and $$$y$$$ must be even, and the evenness of $$$(x,y)$$$ is the evenness of $$$(x/2,y/2)$$$ plus 2.
It can be shown that the ends of any segment on an order $$$n+1$$$ curve have different evenness. Also, the transformation from order $$$n+1$$$ to order $$$n$$$ (rotation by $$$45^\circ$$$ and scaling) reduces the evenness by $$$1$$$ (points with evenness $$$0$$$ transform to non-integer points). When transforming from order $$$n+1$$$ to order $$$n$$$, the position on the segment either doesn't change, or gets subtracted from the length of the segment minus one (where the length of the segment is defined as the number of original segments that map to it).
After a transformation is applied repeatedly, the initial segment will eventually map to one of the segments adjacent to the origin. Subsequent transformations will not change it. At this point, the answer can be easily determined. Here is a complete Python implementation (which gets TL, but an equivalent implementation in C++ or Java works very quickly):