1

有人可以向我解释为什么在以下解决方案中使用 GCD：

http://www.codechef.com/viewsolution/2849602（用于 c）

http://www.codechef.com/viewsolution/2849324（用于 C++）

对于这个问题： http: //www.codechef.com/ACMKAN13/problems/LINEPROB

狙击手站在 2D XY 平面上的点 (x1, y1)。他从他的位置向点 (x2, y2) 射击。您可以假设所有点都是整数。

考虑由 XY 平面上的整数点形成的 2D 网格。Sniper 和 Target 的位置是这个网格中的格点。狙击手射出的子弹会沿着从 (x1, y1) 到 (x2, y2) 的直线轨迹。子弹不超过（x2，y2）。

考虑当狙击手站在 (1, 1) 并且目标位于 (4, 3) 时子弹的轨迹。

在此处输入图像描述

注意子弹的轨迹如何接触 4 个单元格。当且仅当子弹将进入单元格时，才认为该单元格被轨迹触及。子弹的轨迹触及了多少细胞？

 输入

第一行包含一个整数 T，即测试用例的数量。以下 T 行中的每一行都包含一个测试用例。每个测试用例包含 4 个整数 x1、y1、x2 和 y2。整数由单个空格字符分隔。输出

对于每个测试用例，输出一行，其中包含子弹从 (x1, y1) 到 (x2, y2) 的轨迹所触及的细胞数。请记住，当且仅当子弹进入单元格时，才认为一个单元格被弹道接触 - 仅接触一侧是不够的。约束

0 < T < 10100 0 ≤ x1, y1, x2, y2 ≤ 1000000000

样本输入

3 0 0 3 2 0 0 2 2 0 0 1 0

样本输出

4 2 0

4

2 回答 2

4

解决方案背后的逻辑是：

子弹沿 X 轴
穿过的块数，加上子弹沿 Y 轴穿过的
块数，减去被过度计数的块数

给定点(X1, Y1)和(X2, Y2)，让A1 = abs(X1 - X2)和A2 = abs(Y1 - Y2)。然后，不失一般性，我们可以考虑点(0, 0)和(A1, A2)。

请注意，它A1表示子弹沿 X 轴穿过的块数。但是，这也是项目符号在(0, A1]网格上的间隔上触及的垂直线的数量。同理，A2表示子弹沿 Y 轴经过的块数，也表示子弹在区间 上触及的水平线数(0, A2]。

当被视为触摸线的数量时，更容易理解为什么需要减去一些数字。需要减去的数字是对应于在垂直和水平线交叉处发生的触摸的数字。的出现次数由 和 的 GCDA1计算A2。特别是，它发生在 in 的点(k * A1/GCD(A1,A2), k * A2/GCD(A1,A2))上。k1 .. GCD(A1,A2)

于 2013-10-19T16:04:47.940 回答
0

在解释使用背后的逻辑之前，gcd我想澄清一下，这可能不是这段代码的作者所想的确切方式。
首先，我max在该代码中看不到任何函数的使用。
解释：
假设

  1. 狙击手在(0,0)，目标在(3,3)。很明显，子弹的轨迹会接触到2细胞。
    备注：当狙击手和目标在直线上x = y或平行时，接触的单元格比纵坐标（或横坐标）少一个。（这等于子弹行进距离的x和y分量之和减去子弹行进距离的x和y分量的 GCD 。）
  2. 狙击手在(0,0)，目标在(0,3)或(3,0)。再次清楚，通过查看图片，子弹的轨迹将触及0细胞。
    备注：当狙击手和目标在直线上x或y或平行于x或y时，接触的单元格为一个0。（这等于子弹行进距离的x和y分量之和减去子弹行进距离的x和y分量的 GCD 。）
  3. 狙击手在(1,1)，目标在(4,3)。很明显，子弹的轨迹会接触到4细胞。
    备注：在所有其他情况下，单元格数等于子弹行进距离的x和y分量之和减去子弹行进距离的x和y分量的 GCD。
于 2013-10-19T16:19:51.327 回答