P1170 Bugs Bunny and the Hunter

Bugs Bunny is hiding in an orchard next to a forest. The orchard has $M \times N$ trees arranged in an $M$-row by $N$-column grid, and the distance between two horizontally or vertically adjacent trees is $1$. Bugs Bunny is under one of the trees. A hunter carrying a shotgun enters the orchard. He climbs onto a fruit tree, preparing to kill Bugs Bunny. If there is no other fruit tree on the line segment connecting the hunter’s position and Bugs Bunny’s position, then the hunter can see Bugs Bunny. Given the positions of the hunter and Bugs Bunny, write a program to determine whether the rabbit’s position is safe.

The first line contains $n$, the number of test cases. For each test case, the first line contains two positive integers $a_x$ and $a_y$, representing the hunter’s position, and the second line contains two positive integers $b_x$ and $b_y$, representing Bugs Bunny’s position.

Output $n$ lines. Each line contains `yes` or `no`, indicating whether Bugs Bunny’s position is safe.

$1 \le n \le 10^5$, $1 \le a_x, a_y, b_x, b_y \le 10^8$. It is guaranteed that Bugs Bunny and the hunter are not at the same position. Translated by ChatGPT 5