eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Границя

Границя

Ліміт часу 2 секунди
Ліміт використання пам'яті 16 MiB

Прикордонна полоса Ліліпутії являє собою опуклий многокутник з ненульовою площею. Вершинами многокутника є сторожеві вежі, з'єднані між собою прямими лініями. Цей кордон для Ліліпутії є занадто довгим і дорогим для утримання; тому уряд країни вирішив переглянути його, щоб зробити коротшим. Але вони не хочуть будувати нові сторожеві вежі, а використати вже існуючі для нового кордону.

Кожен день охоронці інспектують кордон. Вони обходять вежі одну за одною, рухаючись вздовж кордону за годинниковою стрілкою. Сторожеві вежі пронумеровано числами від 1 до N у відповідності з порядком їх обходу. Перегляд кордону не повинен змінити описаний метод його обходу, а площа Ліліпутії повинна залишатись ненульовою.

Наприклад, кордон на картинці (масштаб задано у кілометрах) можна обійти по шляху 1-2-3-4-5-1, довжина якого 57.89 кілометрів. Для того, щоб зробити довжину границі мінімально можливою, Ліліпутія повинна її переглянути так, щоб обхід можна було здійснити по шляху 2-3-4-2, зменшивши довжину до 27.31 кілометрів.

У Ліліпутії є ряд історичних пам'ятників, які є її головною гордістю. Історичні пам'ятники повинні завжди знаходитись всередині Ліліпутії, і вони не повинні опинись в результаті на кордоні. Вам потрібно розробити план найкоротшого кордону, який дозволить зберегти усі історичні пам'ятники в Ліліпутії.

На картинці два історичних пам'ятники відмічено символами "A" та "B". Щоб зберігти їх всередині Ліліпутії, протрібно провести границю по шляху 1-2-3-4-1 довжиною 51.78 кілометрів.

Вхідні дані

Перший рядок містить два цілих числа N та M, відокремлених пропуском. N (3N50) - загальна кількість веж на границі Ліліпутії. M (0M1000) - загальна кількість історичних монументів всередині Ліліпутії.

Наступні N рядків містять координати сторожевих веж у порядку обходу за годинниковою стрілкою. За ними йдуть M рядків, які містять координати пам'ятників. Усі координати подано парами цілих чисел (X та Y відповідно), відокремлених пропуском. Координати задано у кілометрах, кожне значення не перевищує 10000 за модулем. Усі сторожеві вежі розміщено у різних місцях.

Вихідні дані

Виведіте одне дійсне число – найменшу можливу довжину кордону Ліліпутії (у кілометрах) з точністю до двох десяткових знаків.

Приклад

Вхідні дані #1
5 0
8 9
0 -7
-8 -7
-8 1
-8 9
Вихідні дані #1
27.31
Джерело 2000-2001 ACM Northeastern European Regional Programming Contest