分数: 575 点
问题陈述
瓷砖的布局覆盖二维坐标平面。
每个图块都是一个矩形,并且对于每个整数三元组 (i, j, k) 满意 0 \leq k < K,按照以下规则放置相应的图块:
- 当 i 和 j 具有相同的奇偶性(均为偶数或均为奇数),对应的图块 (i, j, k) 覆盖的区域 iK \leq x \leq (i + 1)K 和 jK + k \leq y \leq jK + k + 1.
- 当 i 和 j 具有不同的奇偶性,对应的图块 (i, j, k) 覆盖的区域 iK + k \leq x \leq iK + k + 1 和 jK \leq y \leq (j + 1)K.
两块瓷砖是 相邻 当它们的边具有正长度的公共段时。
从包含该点的图块开始 (S_x + 0.5, S_y + 0.5),找到需要移动到相邻图块才能到达包含该点的图块的最少次数 (T_x + 0.5, T_y + 0.5).
有 T 测试用例;解决它们中的每一个。
约束
- 1 \leq T \leq 10^4
- 2 \leq K \leq 10^{16}
- -10^{16} \leq S_x, S_y, T_x, T_y \leq 10^{16}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\vdots
\text{case}_T
每个案例均按以下格式给出:
K S_x S_y T_x T_y
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 -2 1 4 -1 4 8 8 0 2 5 -1000000000000 -1000000000000 1000000000000 1000000000000
示例输出 1
4 4 800000000000
让我们解释一下第一个测试用例。
让 (i, j, k) 表示对应于整数三元组的图块 (i, j, k).
(-1.5, 1.5) 包含在图块中 (-1, 0, 1),和 (4.5, -0.5) 包含在图块中 (1, -1, 2).
例如,通过从图块移动 (-1, 0, 1) to (-1, 0, 2) to (0, 0, 2) to (1, 0, 0) to (1, -1, 2),您可以到达瓷砖 (1, -1, 2) 四次移动到相邻的图块。
