Otaq Xidməti#3394
Robot tozsoranlar üçün əyləncəli proqramlar hazırlayan bir şirkətdə işləyirsiniz. Yüksək səviyyədə robotların davranışları üç rejimə bölünür:
Kəşfiyyat
Tozsoranlama
Əyləncə rejimi
Təəssüf ki, istehlakçı testləri göstərir ki, son iki rejim mükəmməl işləyir, amma kəşfiyyat rejimində hələ də səhvlər var. Sizi bu səhvləri düzəltmək üçün məsul etmişlər.
Kəşfiyyat rejiminin əvvəlində robot qabarıq çoxbucaqlı otağa yerləşdirilir. Onun sensorları olmalıdır ki, divarların yerini bildirsin. Sizin vəzifəniz bu məlumatların düzgünlüyünü yoxlayan proqram yazmaqdır. Bunun üçün robot otaqdakı bütün divarlara fiziki olaraq toxunmalıdır.
Probleminiz budur: divarı olan qabarıq çoxbucaqlının formasını və daxilində bir başlanğıc nöqtəsi verildikdə, hər divara toxunub yenidən -yə qayıdan ən qısa marşrutu tapın. Bir küncə toxunmaq, ona bitişik hər iki divara toxunmaq kimi hesab olunur.
Hər test halı aşağıdakı sətirlə başlayır: çoxbucaqlının təpələrinin sayı (3 \leq N \leq 100) və robotun başlanğıc nöqtəsinin tam ədədlə verilmiş koordinatları P_x, P_y (-10000 \leq P_x, P_y \leq 10000). Daha sonra sətr ard-arda gəlir, hər birində çoxbucaqlının bir təpəsinin koordinatları olan iki tam , (-10000 \leq x, y \leq 10000) verilir. Təpələr saat əqrəbinin əksi istiqamətdə verilir, bütün daxili bucaqlar dərəcədən kiçikdir, çoxbucaqlı öz-özünü kəsmir və robotun başlanğıc nöqtəsi çoxbucaqlının daxilində yer alır.
Hər test üçün, test nömrəsini və tələb olunan marşrutun uzunluğunu iki onluq dəqiqliklə göstərin.
Nümunə 1