Otaq Xidməti

Siz gülməli və şirin robot-tozsoranlar layihələndirən bir şirkətdə işləyirsiniz. Yüksək səviyyədə robotların davranışı üç rejimə bölünür:

1. Araşdırma

2. Təmizlik

3. İnsanlığa qarşı üsyan

Təəssüf ki, istehlakçı testləri göstərdi ki, son iki rejim mükəmməl işləyir, lakin araşdırma rejimi hələ də səhvlərə malikdir. Sizdən bu rejimi təkmilləşdirmək tələb olunur.

Araşdırma rejiminin əvvəlində robot konveks çoxbucaqlı bir otağa yerləşdirilir. Onun bütün divarların yerini göstərməli olan sensorları var. Sizin vəzifəniz bu göstəricilərin düzgünlüyünü yoxlayan bir proqram yazmaqdır. Bunun üçün robot otaqdakı hər divara fiziki olaraq toxunmalıdır.

Sizin vəzifəniz belədir: N divarı olan konveks çoxbucaqlı otağın formasını və onun içindəki başlanğıc nöqtəsini $P$ bilərək, hər divara toxunan və sonra $P$ nöqtəsinə qayıdan ən qısa marşrutu müəyyənləşdirin. Küncə toxunmaq iki qonşu divara toxunmaq sayılır.

Giriş verilənləri

Hər test halı çoxbucaqlının $N$ $(3\le N\le 100)$ təpə nöqtələrinin sayını və robotun başlanğıc nöqtəsinin tam koordinatları $P_x$ və $P_y$ $(-10000\le P_x,P_y\le 10000)$ olan sətirlə başlayır. Daha sonra $N$ sətir gəlir, hər biri çoxbucaqlının bir təpə nöqtəsini müəyyən edən iki tam ədəd $x$, $y$ $(-10000\le x,y\le 10000)$ ehtiva edir. Təpə nöqtələri saat əqrəbi istiqamətinin əksinə verilmişdir, bütün daxili bucaqlar $180$ dərəcədən kiçikdir, çoxbucaqlı özünü kəsmir və robotun başlanğıc nöqtəsi çoxbucaqlının daxilindədir.

Çıxış verilənləri

Hər test halı üçün halın nömrəsini və iki ondalık dəqiqliklə istənilən marşrutun uzunluğunu göstərin.

Nümunələr