Задача MainPoint. Міністерство спорту країни вирішило провести справжнє автораллі світового рівня і їм терміново слід вирішити усі організаційні питання. Міністерство намагається виконати певні вимоги до прокладання траси гонок. Чиновники люблять хизуватися цифрами, а тому прагнуть, аби траса була максимальної довжини, а Міністр бажає, щоб траса обов’язково пролягала через столицю. Крім того, аби зменшити ризики і інші неприємні моменти, було вирішено зробити трасу у формі опуклого багатокутника таким чином, щоб повороти (тобто вершини багатокутника) завжди були у якомусь із міст. За наданою мапою міст вам треба віднайти довжину максимального маршруту, який би відповідав вказаним вимогам.
Слід також зазначити, що чиновники Міністерства спорту вважають опуклими також багатокутники, що вироджені у лінію, якщо їх можна отримати, спроектувавши деякий “справжній” багатокутник на якусь із прямих. Тобто, багатокутник (0, 0) - (1, 1) з точки зору Міністерства також опуклий.
Технічні умови. Програма MainPoint читає з пристрою стандартного введення єдине натуральне число - кількість міст (2 ≤ N≤ 10000) . Далі в тому ж рядку через пропуски слідує рівно N пар чисел - координати чергового міста на мапі. Усі координати не перевищують за модулем 5000. Столицею будемо вважати перше з міст.
Програма виводить на пристрій стандартного введення єдине дійсне число з точністю у 3 знаки після коми - максимальна довжина протяжності маршруту, який би задовольнив чиновників.
Приклади
|
Введення |
Виведення |
Коментар |
|
3 0 2 0 0 0 4
|
8.0000000 |
У даному випадку траса вироджена у лінію, але з точки зору чиновників це все одно опуклий багатокутник. |
|
5 0 0 -1 0 4 0 0 3 0 -3 |
16.0000000 |
Найкраща траса: |