Обслуговування номерів#3394

Обслуговування номерів

3 секунди

256 мегабайтів

Дуже складна

Ви працюєте в компанії, яка розробляє милих, кумедних роботів-пилососів. На високому рівні поведінку роботів поділено на три режими:

Дослідження
Прибирання пилу
Режим вечірки

На жаль, під час споживчих тестів з'ясувалося, що останні два режими працюють ідеально, а от режим дослідження ще містить помилки. Вас призначили відповідальним за виправлення цих недоліків.

На початку режиму дослідження робот розташовується у випуклій багатокутній кімнаті. Він має сенсори, які повинні визначати розташування всіх стін. Ваше завдання — написати програму, яка перевіряє правильність цих вимірювань. Для цього робот має фізично торкнутися кожної стіни у кімнаті.

Ваше завдання: знаючи форму випуклої багатокутної кімнати з $N$ стінами та початкову точку $P$ всередині неї, визначте найкоротший маршрут, який торкається кожної стіни, а потім повертається в $P$ . Торкання кута вважається торканням обох суміжних стін.

Вхідні дані

Кожен тестовий випадок починається з рядка, що містить число вершин багатокутника $N$ $(3 \leq N \leq 100)$ (3 \leq N \leq 100) і цілі координати $P_{x}$ P_x та $P_{y}$ P_y початкової точки робота $(- 10000 \leq P_{x}, P_{y} \leq 10000)$ (-10000 \leq P_x, P_y \leq 10000). Далі йдуть $N$ рядків, у кожному з яких містяться по два цілих числа $x$ , $y$ $(- 10000 \leq x, y \leq 10000)$ (-10000 \leq x, y \leq 10000), які задають вершину багатокутника. Вершини перелічені у контргодинниковому порядку, усі внутрішні кути менші за $180$ градусів, багатокутник не самоперетинається, а початкова точка робота розташована строго всередині багатокутника.

Вихідні дані

Для кожного тестового випадку виведіть номер випадку та довжину шуканого маршруту з точністю до двох знаків після коми.

Приклади

Приклад 1