Найдовша доріжка#3565
Міський голова КМ-міста вирішив побудувати нову початкову школу. Ділянка для школи має складну багатокутну форму, що викликало кілька проблем. Найбільшою проблемою став брак місця для короткої бігової доріжки. Ваше завдання — допомогти міському голові КМ визначити максимальну можливу довжину бігової доріжки, яку можна розмістити на ділянці. Доріжку можна розглядати як відрізок прямої лінії, шириною якої можна знехтувати. Межа ділянки має форму простого багатокутника без самоперетинів, і доріжка може торкатися цієї межі. Зверніть увагу, що межа може бути невипуклою.
3 \leq N \leq 100
Кожен тестовий випадок має наступний формат: у першому рядку міститься одне ціле число — кількість вершин багатокутника. Кожен з наступних рядків містить по два цілих числа x_i та y_i, які задають координати вершини багатокутної межі ділянки у порядку проти годинникової стрілки.
-1000 \leq x_i, y_i \leq 1000
Вхідні дані складаються з кількох тестових випадків, після яких слідує рядок, що містить 0.
Для кожного тестового випадку виведіть його номер та максимальну можливу довжину доріжки в одному рядку.
Відповідь повинна бути подана як число з плаваючою комою з абсолютною похибкою не більше 10^{-6}.
Приклад 1