eolymp
bolt
Try our new interface for solving problems
Məsələlər

Конструктор

Конструктор

Мальчику Пете недавно подарили конструктор для сборки роботов Mindrack 2.0. Почитав документацию, Петя решил собрать простой плоттер для рисования фигур. Плоттер представляет собой руку, состоящую из двух плеч, соединенных вращающимся шарниром, и имеющую крепление для карандаша на конце. Рука закреплена на подставке также при помощи шарнира. Дополнительно рука имеет сервоприводы, которые могут поворачивать ее относительно основания и один сегмент относительно другого. Рука устанавливается на подставке с бумагой, на которой можно рисовать различные фигуры. Схематично рука изображена на картинке ниже. \includegraphics{https://static.e-olymp.com/content/59/590c107b449533b07ed79b8b34a847a681dde131.jpg} Для рисования фигур робо-рукой Петя написал программу, которая позволяет рисовать различные замкнутые ломаные по заданному набору координат вершин за счет согласованного управления сервомоторами. При этом рука рисует ломаную, не отрывая карандаш от бумаги. Единственная проблема, с которой столкнулся Петя, заключается в том, что шарниры руки не могут неограниченно проворачиваться. Шарнир в основании может проворачиваться не более чем на \textbf{φ} градусов влево и вправо относительно своего среднего положения. Шарнир, соединяющий плечи, может проворачиваться не более чем на \textbf{θ} градусов в обе стороны относительно положения, когда одно плечо сонаправлено с другим. Поэтому при рисовании ломаных могут возникать ситуации, когда рука не может продолжить рисование без отрыва карандаша от бумаги. В этом случае Пете приходится самостоятельно отсоединять карандаш от руки, переводить ее в новое положение, а затем присоединять карандаш. При этом рука продолжает рисовать ломаную с той же точки, на которой она закончила рисование перед "переключением". Естественно, что Петя хочет минимизировать количество таких ручных "переключений". Предположим, что рука находится на координатной плоскости \textbf{Oxy}, причем она прикреплена к основанию в начале координат. Считается, что в среднем положении рука направлена в направлении оси \textbf{Oy}. Будем считать, что рука состоит из двух отрезков --- длины \textbf{L} и \textbf{l}, соответствующих первому плечу, прикрепляющемуся к основанию, и второму плечу, на конце которого закреплен карандаш. Вам требуется по заданным параметрам руки --- числам \textbf{L}, \textbf{l}, \textbf{φ} и \textbf{θ}, и координатам вершин замкнутой ломаной на плоскости определить минимально необходимое количество ручных переключений руки, которое требуется сделать Пете, чтобы нарисовать данную ломаную, либо определить, что это невозможно. Рука может начинать рисование с любой точки ломаной. Однако после того, как выбрана стартовая точка и направление обхода ломаной при рисовании, менять это направление уже нельзя. Также после переключения рука должна продолжить рисование с той же точки, на которой произошло переключение режима, и в том же направлении. Руке не разрешается проводить карандашом по уже нарисованной части ломаной. В случае, когда ломаная имеет самопересечения либо самокасания, при рисовании не разрешается "перепрыгивать" в таких точках на другую часть ломаной. \InputFile В первой строке входного файла заданы четыре целых неотрицательных числа --- \textbf{L}, \textbf{l}, \textbf{φ} и \textbf{θ} (\textbf{1} ≤ \textbf{L + l} ≤ \textbf{10^4}, \textbf{φ + θ}≤ \textbf{180}). В следующей строке записано целое число \textbf{N} --- количество вершин ломаной (\textbf{3} ≤ \textbf{N} ≤ \textbf{100000}). Далее идут \textbf{N}строк c парами целых чисел \textbf{x_i} и \textbf{y_i} -- декартовыми координатами вершин ломаной. Координаты по модулю не превосходят \textbf{10^4}. Никакие две вершины не совпадают. Считается, что ломаная состоит из отрезков с вершинами (\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 В единственную строку выходного файла необходимо вывести минимально необходимое количество ручных переключений руки для рисования заданной ломаной, либо число \textbf{--1}, если нарисовать ломаную указанным способом невозможно.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 4 90 90
6
-6 2
-3 6
3 6
6 2
3 7
-3 7
Çıxış verilənləri #1
1
Mənbə Очный тур XIII Открытой Всесибирской олимпиады по программированию имени И.В. Поттосина