题目描述
兔八哥躲藏在树林旁边的果园里。果园有 M×N 棵树，组成一个 M 行 N 列的矩阵，水平或垂直相邻的两棵树的距离为 1。兔八哥在一棵果树下。
猎人背着猎枪走进了果园，他爬上一棵果树，准备杀死兔八哥。
如果猎人与兔八哥之间没有其它的果树，猎人就可以看到兔八哥。
现己知猎人和兔八哥的位置，编写程序判断兔子所在的位置是否安全.
输入格式
第一行为 nn，表示有 nn 组数据，每组数据的第一行为两个正整数 ax? 和 ay?，表示猎人的位置，第二行为两个正整数 bx? 和 by?，表示兔八哥的位置。
输出格式
共有 n 行，每行为 yes 或 no 表示兔八哥的位置是否安全。
输入输出样例
输入 #1复制
1
1 1
1 2
输出 #1复制
no
说明/提示
1≤n≤1051≤ax?,ay?,bx?,by?≤108。
解题思路
这道题开始的时候的十分容易误导人，刚读完题目时，我想大部分人应该都认为只有围绕在猎人周围一圈的8个点是危险点。其实这是不完整的。假设猎人是原点除开上诉的8个点以外还有好多例如（2,1）（1,4）等等但是这些点也是有规律可循的。猎人要杀死兔兔只有当他们站的点的坐标差的绝对值互质才会发生。
#include<bits/stdc++.h>
using namespace std;
int n, rx, ry, lrx, lry;
int gcd(int x, int y)
{
?? ?if (y == 0) return x;
?? ?else return (gcd(y, x % y));
}
int main()
{
?? ?cin >> n;
?? ?for (int i = 1; i <= n; i++)
?? ?{
?? ??? ?cin >> lrx >> lry >> rx >> ry;
?? ??? ?if (gcd(abs(lrx - rx), abs(lry - ry)) == 1) cout << "no\n";
?? ??? ?else cout << "yes\n";
?? ?}
?? ?return 0;
}
计算机202 yjq
|