打獵
這題為啥貼，因為思路太細細細啦！！！
森林里有M×N棵樹，組成一個M行N列的矩陣，水平或垂直相鄰的兩棵樹的距離為1，獵人和熊分別在一棵樹下，如果獵人與熊之間沒有其它的樹遮擋視線，獵人就可以開槍打到熊，
己知獵人和熊的位置，試判斷熊所在的位置是否安全，
第一行為n，表示有n(n≤100000)組資料，每組資料均為一行，分別為四個正整數，分別表示獵人和熊的x坐標和y坐標(1≤坐標值≤100 000 000)，
輸出n行，每行為“yes”或“no”，表示熊的位置是否安全，
自己做的時候：思路：判斷斜率不存在和為零的時候，然后直線方程求 k b ，然后看看 y 是不是 整數，有bug，存在于斜率和b有可能本身就是無限小數
然后就：我是傻X……
優秀思路：先來代碼
// 也就是形成的三角形兩直角邊互質
// 證明：如果兩點之間有且只有一個整數點（其他情況可以轉化成這種情況），
// 那么這個整數點必然是中點，gcd（a，b）==2 （其他情況gcd（a，b）> 2,
// 原因：只有一個整數點，說明 a點到ab邊上一整數點c 之間無整數點
// （ab為斜邊，c為ab上一點），
// 最近的下一個整數點就應該是 b ，如果不是b ，兩種情況，cb比ac小，ac本身就是最小，
// 比它小顯然不存在這樣一個整數點，cb比ac大，b點本身是一個整數點，還存在一個d
// （d在cb之間，使得 ac==cd，d是一個整數點，b也是，不符合ab之間只有有一個整數點的
// 前提
// 結論：ab之間有整數點，gcd（a，b）>=2（歡迎指正）
// 而且 你不用判斷構不成三角形的情況
// 因為 gcd（1，0）==1 no
// gcd（2，0）==2 yes 剛剛好
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const LL INF=0x3f3f3f3f;
const LL NN=1e7+9;
const LL N=2e5+5;
LL gcd(LL x,LL y)
{
if(!y) return x;
return gcd(y,x%y);
}
int main()
{
LL t;
cin>>t;
while(t--)
{
LL x,y,xx,yy;
cin>>x>>y>>xx>>yy;
if(gcd(abs(x-xx),abs(yy-y))==1) cout<<"no";
else cout<<"yes";
if(t) putchar(10);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/259992.html
標籤：其他