Luo Gu P1170 Bugs Bunny and Hunter

Title Description

Bugs Bunny hid in the orchard next to the forest . The orchard has M×N tree , Form a M That's ok N Columns of the matrix , The distance between two horizontally or vertically adjacent trees is 1. Bugs Bunny is under a fruit tree .

The hunter walked into the orchard with his shotgun on his back , He climbed up a fruit tree , Ready to kill bugs bunny .

If there are no other fruit trees between the hunter and Bugs Bunny , The hunter can see bugs bunny .

Now we know the location of the hunter and bugs bunny , Write a program to determine whether the location of the rabbit is safe .

Input format

First act nn, Express nn Group data , The first line of each set of data is two positive integers ax​ and ay​, Indicates the location of the Hunter , The second line is two positive integers bx​ and by​, Indicates the location of bugs bunny .

Output format

share n That's ok , Every act yes or no Indicates whether Bugs Bunny's position is safe .

I/o sample

Input #1 Copy

1
1 1
1 2

Output #1 Copy

no

explain / Tips

1≤n≤1051≤ax​,ay​,bx​,by​≤108.

Their thinking

This question is very misleading at the beginning , When I just finished reading the topic , I think most people should think that there is only one circle around the hunter 8 One point is dangerous . In fact, this is incomplete . Suppose the hunter is the origin except for the appeal 8 There are many other points besides, for example （2,1）（1,4） Wait, but these points also have rules to follow . Hunters want to kill rabbits. Rabbits only happen when the absolute value of the coordinate difference of their stations is mutual prime .

#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;
}

Computer 202 yjq