Три зірки
Limits: 4 sec., 256 MiB
Зеник із Марічкою розглядають чисте нічне небо, на якому Марічка побачила \(n\) зірок. Зірки можна зобразити як точки на площині із координатами \((x_i, y_i)\) для усіх \(i\) від 1 до \(n\) включно.
Вона попросила Зеника знайти таку трійку різних зірок \(A\), \(B\) та \(C\), аби мінімізувати суму \(AB + BC\), де \(AB\) — відстань від зірки \(A\) до зірки \(B\), а \(BC\) — відстань від зірки \(B\) до зірки \(C\).
Ваше завдання — знайти цю мінімальну сумарну відстань.
Input
У першому рядку задано одне ціле число — кількість зірок, які видно на нічному небі.
У наступних \(n\) рядках задано пари цілих чисел \(x_i\) та \(y_i\) через пробіли — координати зірок на площині.
Output
Виведіть одне дійсне число — шукану мінімальну суму відстаней.
Відповідь вважатиметься правильною, якщо абсолютна або відносна похибка не перевищує \(10^{-11}\).
Constraints
\(3 \le n \le 1500\),
\(|x_i, y_i| \le 10^9\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 1 1 4 7 7 11 7 4 | 9.24264068712 |
Notes
Найкраще вибрати третю, другу та четверту точки. Відстань від третьої до другої рівна \(\sqrt{25} = 5\), а від другої до четвертої — \(\sqrt{18}\), отже відповідь рівна \(5 + \sqrt{18} \approx 9.24264068712\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|