eolymp
bolt
Try our new interface for solving problems
Problems

Plotter

Plotter

Pete’s parents got him the Mindrack 2.0 kit for building robots. Pete read the manual and decided to build a simple plotter to draw shapes. The plotter is a mechanical arm consisting of two segments with rotary joint and a slot for a pencil in the distal end. The arm is attached to a base using a joint too. Additionally the arm has servos that can rotate it relative to the base and turn segments relative to each other. The arm can draw various shapes on paper. Below is a schematic illustration: \includegraphics{https://static.e-olymp.com/content/59/590c107b449533b07ed79b8b34a847a681dde131.jpg} Pete wrote a program that allows drawing various closed polylines based on a given set of points by means of coordinated actions of the servos. The arm can draw a polyline without taking the pencil off the paper. The only problem Pete has encountered is the limited mobility of the arm segments. The basal joint can turn no more than \textbf{φ} degrees left and right relative to its central position and the joint connecting the segments cannot turn more than \textbf{θ} degrees relative to the codirectional alignment of the segments. For that reason a situation can occur during drawing shapes when the robotic arm is unable to continue drawing without lifting the pencil from paper. In this case Pete has to disconnect the pencil manually, switch the arm into a new configuration and reconnect the pencil. The arm then continues drawing the polyline from the same point where it has ended drawing before manual switching. Naturally, Pete wants to minimize the amount of such manual switches. Let the arm be positioned in the \textbf{Oxy}, reference plane and attached to its origin. Then the centra position of the arm is directed along the \textbf{Oy}. axis. Assume the arm consists of two segments with the lengths \textbf{L} and \textbf{l}, corresponding to the basal segment attached to the base and distal segment holding the pencil. Given the parameters of the arm --- the numbers \textbf{L}, \textbf{l}, \textbf{φ} and \textbf{θ}, and coordinates of polyline points on the plane you have to calculate the minimal number of manual arm switches necessary to draw the polyline or determine that it is impossible. The arm can begin drawing from any point of the polyline and in any of the two directions. However, once the start point and the drawing direction have been selected the latter cannot be changed. In case of the switch, the arm must continue drawing from the same point where switching has occurred and in the same direction as before. If the polyline has self-intersections or self-contacts, then the arm is not allowed to switch to another polyline part at such points, it still must draw polyline segments in the prescribed order taking into account the chosen direction and starting point. \InputFile The first line of the input file contains four nonnegative numbers --- \textbf{L}, \textbf{l}, \textbf{φ} and \textbf{θ} (\textbf{1} ≤ \textbf{L + l} ≤ \textbf{10^4}, \textbf{φ + θ }≤ \textbf{180}). The next line contains an integer \textbf{N} --- the number of points in the closed polyline (\textbf{3} ≤ \textbf{N} ≤ \textbf{100000}). The next \textbf{N lines contain pairs of integers} \textbf{x_i} and \textbf{y_i} -- Cartesian coordinates of the polyline points. The absolute values of coordinates do not exceed \textbf{10^4}. No two points coincide. It is assumed that the polyline consists of the segments (\textbf{x_1},\textbf{y_1})−(\textbf{x_2}, \textbf{y_2}), (\textbf{x_2}, \textbf{y_2})−(\textbf{x_3}, \textbf{y_3}), …, (\textbf{x_\{N−1\}}, \textbf{y_\{N−1\}})−(\textbf{x_N}, \textbf{y_N}) и (\textbf{x_N}, \textbf{y_N})−(\textbf{x_1}, \textbf{y_1}). \OutputFile The single line of the output file must contain the minimal number of manual switches of the arm necessary to draw the given polyline, or the number \textbf{--1} if it is impossible to draw the polyline using the method described above.
Time limit 1 second
Memory limit 64 MiB
Input example #1
4 4 90 90
6
-6 2
-3 6
3 6
6 2
3 7
-3 7
Output example #1
1
Source XIII All-Siberian Programming Contest named after I.V.Pottosin, November 11, 2012