The Great Escape

Little Yang is tired of his relatives’ constant supervision and has decided to break out of his home – which is modeled as a \(n \times m\) rectangle with its bottom‐left corner at \( (0,0) \) and its top‐right corner at \( (x_1,y_1) \). There are several relatives stationed strictly in the interior of the house. Each point in the house is monitored by the relative (or relatives, in a tie) whose Euclidean distance from that point is the smallest. Initially, Little Yang is uniquely monitored by one relative. In order to escape undetected by as many different relatives as possible, he must choose a continuous path – the coordinates of every point on the path may be real numbers – from his starting point \( (x_0,y_0) \) to any point on the boundary of the rectangle so that the number of different relatives that monitor some point along the path is minimized.

For example, if at point \( (3,3) \) relative A at \( (3,0) \) is at distance 3 and relative B at \( (6,7) \) is at distance 5, then only A monitors this point. However, if at some location two or more relatives are both (equally) the closest, then that location is monitored by all of them. Little Yang’s goal is to find an escape route such that the total number of distinct relatives who end up watching him along the route is as small as possible.

Note: It is guaranteed that the starting point is uniquely monitored by one relative.

inputFormat

The input consists of several lines:

1. The first line contains two real numbers \(x_1\) and \(y_1\) representing the top‐right corner of the rectangle. The bottom‐left corner is \( (0,0) \).
2. The second line contains two real numbers \(x_0\) and \(y_0\), the coordinates of Little Yang’s starting position.
3. The third line contains an integer \(n\) indicating the number of relatives (also the number of interior points).
4. Each of the next \(n\) lines contains two real numbers representing the coordinates of a relative. All relative positions are distinct and lie strictly inside the rectangle.

outputFormat

Output a single integer: the minimum number of distinct relatives who will have monitored Little Yang along some escape route from his starting position to the boundary. If no escape is possible, output -1.

sample

10 10
5 5
1
5 2

1