Конструктор

Батьки Петі подарували йому набір Mindrack 2.0 для складання роботів. Петя прочитав інструкцію і вирішив зібрати простий плоттер для малювання фігур. Плоттер — це механічна рука, що складається з двох сегментів з обертовим шарніром і гніздом для олівця на дальньому кінці. Рука кріпиться до основи за допомогою шарніра. Крім того, рука оснащена сервоприводами, які дозволяють їй обертатися відносно основи і повертати сегменти відносно один одного. Рука може малювати різні фігури на папері. На схемі нижче показано будову:

Петя написав програму, яка дозволяє малювати різні замкнені ламані за заданим набором точок шляхом скоординованих дій сервоприводів. Рука може провести ламану, не відриваючи олівця від паперу. Єдина проблема, з якою зіткнувся Петя, — це обмежена рухливість сегментів руки. Базовий шарнір може повертатися не більше ніж на $\phi$ градусів ліворуч і праворуч від центрального положення, а шарнір, що з'єднує сегменти, не може повертатися більш ніж на $\theta$ градусів відносно співнаправленого розташування сегментів. Через це при малюванні може виникнути ситуація, коли роботизована рука не здатна продовжувати малювання, не відриваючи олівця від паперу. У такому випадку Петі доводиться вручну від’єднати олівець, перевести руку у нову конфігурацію і знову приєднати олівець. Після цього рука продовжує малювання ламаної з тієї ж точки, на якій зупинилася до ручного перемикання. Природно, Петя прагне мінімізувати кількість таких ручних перемикань.

Нехай рука розташована у площині $Oxy$ та прикріплена у її початку координат. Центральне положення руки спрямоване вздовж осі $Oy$. Вважається, що рука складається з двох сегментів довжинами $L$ і $l$, відповідно базового сегмента, закріпленого до основи, та дальнього сегмента з олівцем. За заданими параметрами руки — числами $L$, $l$, $\phi$, $\theta$ та координатами точок ламаної на площині — необхідно обчислити мінімальну кількість ручних перемикань, потрібних для малювання ламаної, або встановити, що це неможливо. Починати малювання рука може з будь-якої точки ламаної й у будь-якому із двох напрямків. Однак після вибору початкової точки і напряму малювання їх змінювати не можна. У разі перемикання рука повинна продовжувати малювання з тієї ж точки та в тому ж напрямку, що й до перемикання. Якщо у ламаної є самоперетини чи самодотики, руці не дозволено переходити на іншу частину ламаної в цих точках; вона повинна продовжувати малювати сегменти ламаної у визначеній послідовності з урахуванням обраного напрямку та початкової точки.