【数学】兔八哥与猎人

题目

P1170 兔八哥与猎人

题目描述

兔八哥躲藏在树林旁边的果园里。果园有 $M \times N$ 棵树，组成一个 $M$ 行 $N$ 列的矩阵，水平或垂直相邻的两棵树的距离为 $1$ 。兔八哥在一棵果树下。

猎人背着猎枪走进了果园，他爬上一棵果树，准备杀死兔八哥。

如果猎人与兔八哥之间没有其它的果树，猎人就可以看到兔八哥。

现己知猎人和兔八哥的位置，编写程序判断兔子所在的位置是否安全.

输入格式

第一行为 $n$ ，表示有 $n$ 组数据，每组数据的第一行为两个正整数 $a_x$ 和 $a_y$ ，表示猎人的位置，第二行为两个正整数 $b_x$ 和 $b_y$ ，表示兔八哥的位置。

输出格式

共有 $n$ 行，每行为 yes 或 no 表示兔八哥的位置是否安全。

样例 #1

样例输入 #1

1
1 1
1 2

样例输出 #1

no

提示

$1\le n \le 10^5$ ， $1 \le a_x, a_y, b_x, b_y \le 10^8$ 。

解题

方法一：数学

思路

一开始我以为只要检查猎人周围的八个点，如果兔八哥没在这八个点中就说明位置安全，但在 WA 了一次之后发现：只有两点连成的线段之间（不包括线段两端）不存在整数点时，位置才算得上是安全，例如下图：

现在考虑点 $(a_x, a_y)$ 和 $(b_x, b_y)$ 之间的线段。我们可以将这条线段看作是从 $(a_x, a_y)$ 出发，朝着 $(b_x, b_y)$ 移动的过程。我们可以在该线段上选择一个整数点，该点的坐标可以表示为 $(x, y)$ ，其中 $x$ 和 $y$ 分别表示在 $x$ 和 $y$ 方向上移动的步数。我们可以用以下方式计算 $x$ 和 $y$ ：

计算 $x$ ：我们知道 $|a_x - b_x|$ 可以被 $d$ 整除，因此存在整数 $k$ ，使得 $|a_x - b_x| = kd$ 。那么我们可以写出：
$x = a_x + kt$ ，其中 $t$ 是一个整数。
计算 $y$ ：同样地， $|a_y - b_y|$ 可以被 $d$ 整除，存在整数 $l$ ，使得 $|a_y - b_y| = ld$ 。那么我们可以写出：
$y = a_y + lt$ ，其中 $t$ 是一个整数。

现在，我们看到 $(x, y)$ 的坐标是由 $t$ 决定的，而 $t$ 可以是任何整数。这意味着我们可以在该线段上选择一个整数点 $(x, y)$ ，因为我们可以选择适当的整数 $t$ 使得 $(x, y)$ 的坐标都是整数。因此，该线段上至少存在一个整数点，证明了原陈述的正确性。

代码

#include <cstdio>
#include <cmath>

using namespace std;

int n, ax, ay, bx, by;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    scanf("%d", &n);
    while (n--) {
        scanf("%d%d%d%d", &ax, &ay, &bx, &by);
        puts(gcd(abs(ax - bx), abs(ay - by)) != 1 ? "yes" : "no");
    }

    return 0;
}

目录CONTENT

【数学】兔八哥与猎人

题目

解题

方法一：数学

思路

代码

参考

评论区