← 返回题目列表

Codeforces · 1578/D

D. 龙曲线

中文机器翻译题面 查看原题

龙曲线是一条自相似的分形曲线。在这个问题中,它是由相同长度的直线段以直角连接而成的曲线。构造龙曲线的简单方法如下:取一条纸条,将其沿同一方向对折 $$$n$$$ 次,然后部分展开,使各部分以直角连接。如下所示:

在此示例中,构造了 $$$3$$$ 阶的龙曲线。一般来说,高阶龙曲线都会有低阶龙曲线作为前缀。这使得我们可以定义无限阶龙曲线,当阶数接近无穷大时,这是有限阶龙曲线的极限。

考虑四条无限阶龙曲线。每条线都从原点(点$$$(0,0)$$$)开始,每条线段的长度为$$$\sqrt2$$$。曲线的第一段分别结束于点 $$$(1,1)$$$、$$$(-1,1)$$$、$$$(-1,-1)$$$ 和 $$$(1,-1)$$$。每条曲线的第一个转弯都是左转(即第一条曲线的第二段结束于点 $$$(0,2)$$$)。在这种情况下,每个线段都是一个坐标为整数的轴对齐单位正方形的对角线,并且可以证明恰好有一个线段穿过每个这样的正方形。

给定一个点 $$$(x,y)$$$,您的任务是找到穿过对角分别为 $$$(x,y)$$$ 和 $$$(x+1,y+1)$$$ 的正方形的线段,以及该线段在该曲线上的位置。曲线编号为 $$$1$$$ 到 $$$4$$$。曲线 $$$1$$$ 穿过 $$$(1,1)$$$、$$$2$$$ 穿过 $$$(-1,1)$$$、$$$3$$$ 穿过 $$$(-1,-1)$$$ 以及 $$$4$$$ 穿过 $$$(1,-1)$$$。这些段的编号从 $$$1$$$ 开始。

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le2\cdot10^5$$$) — 测试用例的数量。

以下 $$$n$$$ 行均包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$-10^9\le x,y\le10^9$$$) — 坐标。

输出

对于每个测试用例,打印一行包含两个整数 - 第一个是曲线的索引($$$1$$$ 和 $$$4$$$ 之间的整数,含),第二个是曲线上的位置(第一段的位置为 $$$1$$$)。

示例

输入 #1

5
0 0
-2 0
-7 -7
5 -9
9 9

输出 #1

1 1
2 2
3 189
4 186
2 68

注意

您可以使用此插图来调试您的解决方案: