Description

The Gaokao is coming again. For those who don’t study hard, this is really bad news. To make Xiao Yang study at home, his relatives decide to stay at his house and watch him: grandpa and grandma, maternal grandparents, uncle, sister-in-law, aunt, and so on.

Xiao Yang can’t stand it anymore. What’s the difference between this life and prison? For his beloved Xiao Hong and for his Dota, he decides to break out!

Assume Xiao Yang’s house is a rectangle with lower-left corner at $(0,0)$ and upper-right corner at $(x_1,y_1)$. There are $n$ relatives staying inside the rectangle (at distinct positions, and none of them lies on the boundary). Every location in the house is watched by the nearest relative(s):

That is, suppose Xiao Yang is at $(3,3)$, relative $A$ is at $(3,0)$, then the distance from $A$ to Xiao Yang is $3$; relative $B$ is at $(6,7)$, then the distance from $B$ to Xiao Yang is $5$. Since $\text{dist}(A) < \text{dist}(B)$, the position $(3,3)$ is watched by $A$.

If there are multiple relatives tying for the nearest distance, then that position is watched by all of them simultaneously.

Given Xiao Yang’s starting position $(x_0,y_0)$. Since the fewer people who discover him, the greater the chance of a successful escape, your task is to design a route from his starting position to the boundary of the rectangle so that the number of people who discover him is minimized.

Xiao Yang may move in any direction; the route can be any continuous path, and all positions along the path may have real coordinates.

It is guaranteed that at the starting position, Xiao Yang is watched by exactly one relative.

Input Format

• The first line contains a positive integer $t \le 3$, the number of testdata.
• For each of the $t$ testdata:
  • The first line contains an integer $n$, the number of relatives.
  • The second line contains four positive integers giving the rectangle’s upper-right corner $(x_1,y_1)$ and Xiao Yang’s starting position $(x_0,y_0)$.
  • Each of the next $n$ lines contains two positive integers, the position of one relative.

Output Format

For each testdata, output a single positive integer: the minimum possible number of relatives who will discover Xiao Yang during his escape.

2
4
10 10 5 5
5 6
3 5
7 5
5 3
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11

1
2

Hint

Explanation:

• In the first dataset, Xiao Yang goes straight up and is only watched by $(5,6)$.
• In the second dataset, Xiao Yang is watched by $(7,7)$, goes to $(9,9)$ where he is watched by $(7,11)$, and then goes straight up.

Constraints:

• For the first $50\%$ of the testdata, $n \le 200$.
• For the remaining testdata, $n \le 600$.

Translated by ChatGPT 5