Konstruktor#4169

Konstruktor

1 saniyə

64 meqabayt

Çətin

Pete-nin valideynləri ona robotlar qurmaq üçün Mindrack 2.0 dəstini alıblar. Pete təlimatı oxudu və fiqurlar çəkmək üçün sadə bir plotter qurmağa qərar verdi. Plotter fırlanan oynağı və distal ucunda karandaş üçün yeri olan iki seqmentdən ibarət mexaniki qol hissəsidir. Qol baza birləşməsi ilə baza hissəsinə birləşdirilib. Bundan əlavə, qolun bazaya nisbətən və seqmentlərin bir-birinə nisbətən dönməsi üçün servomexanizmlər var. Qol kağız üzərində müxtəlif fiqurlar çəkə bilir. Aşağıda sxematik təsvir göstərilmişdir:

Pete proqram yazıb ki, verilmiş nöqtələr toplusuna əsasən müxtəlif bağlı poliliniyaları servoların koordinə edilmiş hərəkətləri ilə çəkmək olur. Qol karandaşı kağızdan qaldırmadan poliliniyanı çəkə bilər. Pete-nin yeganə problemi qol seqmentlərinin hərəkət məhdudiyyətidir. Baza oynağı mərkəzi vəziyyətindən sağa və sola ən çox $φ$ dərəcə dönə bilər, və seqmentləri birləşdirən oynaq isə onların eyni istiqamətə yönəlmiş vəziyyətinə nisbətən ən çox $θ$ dərəcə dönə bilər. Buna görə də, çəkim zamanı, robot qolunun karandaşı qaldırmadan davam etməsi mümkün olmayan vəziyyət yarana bilər. Bu halda, Pete qədim karandaşı əl ilə ayırmalıdır, qolu yeni bir konfiqurasiyaya gətirib karandaşı yenidən qoşmalıdır. Sonra qol poliliniyanı çəkməyə dayandığı yerdən davam etdirir. Təbi olaraq, Pete belə əl dəyişikliklərinin sayını minimum etmək istəyir.

Qoy qol $O x y$ koordinat müstəvisində yerləşdirilmiş olsun və mənşəyə birləşdirilmiş olsun. Qolun mərkəzi vəziyyəti $O y$ oxu boyunca yönəlib. Qoy qol uzunluqları $L$ və $l$ olan iki seqmentdən ibarət olsun; burada $L$ baza seqmentinin (bazaya birləşmiş), $l$ distal seqmentin (karandaşı tutan) uzunluğudur. Qola aid parametrlər — $L$ , $l$ , $φ$ , və $θ$ ədədləri, həmçinin poliliniya nöqtələrinin koordinatları verildikdə, poliliniyanı çəkmək üçün lazım olan minimal əl dəyişikliklərinin (manuel keçidlərin) sayını hesablamaq və ya bunun mümkün olmadığını müəyyən etmək lazımdır. Qol poliliniyanın istənilən nöqtəsindən və istənilən iki istiqamətdən birindən çəkməyə başlaya bilər. Lakin başlanğıc nöqtə və istiqamət seçildikdən sonra, daha dəyişdirilə bilməz. Əgər keçid lazımdırsa, qol mütləq eyni nöqtədən və əvvəlki istiqamətdə çəkməyə davam etməlidir. Əgər poliliniyanın özünü kəsməsi və ya özünə toxunması varsa, qol belə nöqtələrdə başqa hissəyə keçə bilməz; yenə də əvvəl seçilmiş nöqtə ardıcıllığı, başlanğıc və istiqamətə riayət olunmalıdır.

Giriş

Giriş faylının ilk sətrində dörd qeyri-məнfi rəqəm — $L$ , $l$ , $φ$ , və $θ$ ( $1 \leq L + l \leq 1 0^{4}$ 1 \leq L + l \leq 10^4, $φ + θ \leq 180$ \varphi + \theta \leq 180) verilir. Növbəti sətirdə $N$ — bağlı poliliniyada nöqtələrin sayı verilir ( $3 \leq N \leq 100000$ 3 \leq N \leq 100000). Sonra ardıcıl $N$ sətirdə $x_{i}$ x_i və $y_{i}$ y_i tam ədədləri verilir — poliliniya nöqtələrinin Kartezi koordinatları. Koordinatların modulu $1 0^{4}$ 10^4-dən çox deyil. Heç iki nöqtə üst-üstə düşmür. Poliliniya aşağıdakı hissələrdən ibarət sayılır: $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1)-(x_2, y_2), $(x_{2}, y_{2}) - (x_{3}, y_{3})$ (x_2, y_2)-(x_3, y_3), $\dots$ , $(x_{N - 1}, y_{N - 1}) - (x_{N}, y_{N})$ (x_{N-1}, y_{N-1})-(x_N, y_N) və $(x_{N}, y_{N}) - (x_{1}, y_{1})$ (x_N, y_N)-(x_1, y_1).

Çıxış

Çıxış faylının yeganə sətrində poliliniyanı çəkə bilmək üçün tələb olunan minimal əl dəyişikliklərinin (manuel keçidlərin) sayı, əgər mümkünsüzdürsə isə –1 yazılmalıdır.

Nümunələr

Nümunə 1