DMOPC '19 Contest 4 P4 - Math Class

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, \ldots , a_N. One operation is defined as choosing some index i and rotating the token an arbitrary angle around a_i. However, if Veshy previously performed an operation on index i, he only allowed to perform an operation on index j such that 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% of points]

N = 1

Subtask 2 [10% of points]

1 \le N \le 2

Subtask 3 [25% of points]

1 \le N \le 15

Subtask 4 [60% of points]

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.