ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1143. Electric Path

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

At the team competition of the 10th national student informatics Olympic, which is organized at Hanoi National University, there are N teams participating. Each team is assigned to work in a camp. On the map, it can be seen that the camps are positioned on the vertices of a convex polygon with N vertices: P1, P2, …, PN (the vertices are enumerated around the polygon in counter-clockwise order.) In order to achieve absolute safety providing electricity to the camps, besides an electric supplying system, the host organization set up a path from a reserved electricity generator (which is placed in one of the camps) to every camp once, and the path's total length is minimum.

Задача

Given the coordinates of the polygons' vertices (the camps' positions), determine the length of the electric path corresponding to the host organization's arrangement.

Исходные данные

The first line contains the integer N (1 ≤ N ≤ 200). The i'th line of the next N lines contains two real numbers xi, yi, separated by a space, with no more than 3 digits after the decimal points, are vertex Pi's coordinates on the plane (with i = 1, 2, …, N). The length of the path connecting two vertex (xi, yi) and (xj, yj) is computed with the formula: sqrt((xixj)2 + (yiyj)2).

Результат

The only line should contain real number L (written in real number format, with 3 digits after the decimal point), which is the total length of the electric path.

Пример

исходные данныерезультат
4
50.0 1.0
5.0 1.0
0.0 0.0
45.0 0.0
50.211
Источник задачи: The competition for selecting the Vietnam IOI team