DMOPC '19 Contest 4 P4 - Math Class

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

Veshy is taking a class in linear algebra! He comes across a problem about the rotations of points with respect to the origin. However, he deems this too trivial so he comes up with the following problem instead:

Veshy chooses two points located at integer coordinates, A and B, on the 2D plane. There is initially a token at A. Veshy also has a sequence of N points, all located at integer coordinates, on this plane, a_1, a_2, \dots, a_N. One operation is defined as choosing some index i and rotating the token by an arbitrary angle around a_i. However, if Veshy previously performed an operation on index i, he is only allowed to perform an operation on index j if j>i. Determine if it's possible to move the token from A to B, and if so, the minimum number of operations required.


In all subtasks,
1 \le N \le 500
The absolute value of all coordinates will be less than or equal to 10^9.

Subtask 1 [5%]

N = 1

Subtask 2 [10%]

1 \le N \le 2

Subtask 3 [25%]

1 \le N \le 15

Subtask 4 [60%]

No additional constraints.

Input Specification

The first line contains one integer, N.
The second line contains two space-separated integers, A_x and A_y, the coordinates of point A.
The third line contains two space-separated integers, B_x and B_y, the coordinates of point B.
The next N lines contain two space-separated integers, x_i and y_i the coordinates of point a_i.

Output Specification

Output one line containing one integer, the minimum number of operations if it's possible and -1 otherwise.

Sample Input

0 0
4 0
1 0
2 3
3 0

Sample Output


Explanation for Sample Output

One sequence of operations would be to rotate the token 180^\circ around a_1 and then another 180^\circ around a_3. This sequence is shown in green. This would require two operations.
Another sequence would be rotating the token 67.38^\circ counter-clockwise around a_2. This sequence is shown in blue. This would require one operation and it can be shown that there is no shorter sequence.


There are no comments at the moment.