Ants

Mr. Chopsticks found a lot of ants and ant nests on Mars. The behavior of these ants seems quite different from ants on earth, so Mr. Chopsticks built a laboratory to study them. In the laboratory, there is a flat land and N ant nests, numbered from 1 to N, on it. The ith nest’s location is (xi, yi), and no two nests are at the same location. After a period of observation, Mr. Chopsticks has found some laws which all the moving ants obey:

1.  When an ant is at a nest p, it always moves to another nest which is closest to p. If there are multiple nests with minimum distance from p, it moves to the one with smaller x-coordinate value. If there is still a tie, the one with smaller y-coordinate value is chosen. When an ant moves from a nest to another, it always moves along the segment connecting them.

2.  An ant never stops, that is, when an ant arrives at a nest, it moves to the next nest immediately. So, of course, an ant may visit a nest infinitely many times.

3.  All the ants move at the same speed.

What happens if two ants meet each other? Will they fight? Mr. Chopsticks is curious about these questions. But at first, he should know whether two ants will meet. So he considers the following question: Given two different nests, if two ants start to move from these two nests simultaneously, will they meet at some time during their moving?
Note that all the ants and nests can be considered as points.

The input begins with an integer T (T <= 10), indicating the number of test cases. Each case begins with an integer N and Q (2 <= N <= 100000, 1 <= Q <= 100000), indicating the number of ant nests and the number of queries respectively. The following N lines, each contain two integers xi and yi (-1 000 000 000 <= xi, yi <= 1 000 000 000), indicating the location of the ith ant nest. The following Q lines each contain two integers i and j (1 <= i, j <= N, i ≠ j), indicating the number of the two given ant nests.

For each case, output "Case #X:" in a line where X is the case number, staring from 1. Then for each query, output “YES” in a line if the two ants will meet; otherwise output “NO”.

2
2 1
0 0
-1 1
1 2
5 2
1 1
3 3
4 4
0 -3
0 -4
1 3
2 4

Case #1:
YES
Case #2:
YES
NO

SYSU

2016 Multi-University Training Contest 7