Найдовший рядок
Мер міста KM, пан KM, вирішив побудувати нову початкову школу. Ділянка для школи має незручну багатокутну форму, що спричинило кілька проблем. Найсерйознішою з них є нестача місця для короткої бігової доріжки. Ваше завдання — допомогти пану KM обчислити максимальну можливу довжину бігової доріжки, яку можна побудувати на ділянці. Доріжка може розглядатися як відрізок прямої, ширина якого може бути проігнорована. Межа ділянки має просту багатокутну форму без самоперетинів, і доріжка може торкатися межі. Зверніть увагу, що межа може бути не опуклою.
Вхідні дані
N
3 ≤ N ≤ 100
N
x_i
y_i
−1000 ≤ x_i, y_i ≤ 1000
Вхідні дані складаються з кількох тестових випадків, за якими слідує рядок, що містить "0". Кожен тестовий випадок має наступний формат. Перша строка містить ціле число (N). Кожна з наступних (N) рядків містить два цілі числа (x_i) та (y_i), які описують координати вершини багатокутної межі ділянки, у порядку проти годинникової стрілки.
Вихідні дані
10^-6
Для кожного тестового випадку виведіть номер випадку та максимальну можливу довжину доріжки в рядку. Відповідь повинна бути подана як число з плаваючою комою з абсолютною похибкою не більше (10^-6).