Квадрат#3502

Квадрат

1 секунда

64 мегабайти

Середня

Дано квадрат на $[0, 1] \times [0, 1]$ [0, 1] \times [0, 1], в якому розміщено $N$ точок ( $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, P_N) (можна припустити, що різні точки можуть займати одну й ту ж позицію). Ми можемо з'єднати $N$ точок і чотири кути квадрата відрізками так, щоб через ці відрізки будь-які дві з $N + 4$ N + 4 точок могли досягти одна одну (безпосередньо або опосередковано). Довжина графа визначається як загальна довжина цих відрізків. Коли позиції $N$ точок фіксовані, існує спосіб їх з'єднання, який забезпечує найменшу довжину графа. Ми можемо позначити цю довжину як $LEN (P_{1}, P_{2}, \dots, P_{N})$ \mathrm{LEN}(P_1, P_2, \ldots, P_N).

У цій ситуації $LEN (P_{1}, P_{2}, \dots, P_{N})$ \mathrm{LEN}(P_1, P_2, \ldots, P_N) є функцією від $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, P_N. Коли $P_{1}, P_{2}, \dots, P_{N}$ P_1, P_2, \ldots, P_N змінюють свої позиції, $LEN (P_{1}, P_{2}, \dots, P_{N})$ \mathrm{LEN}(P_1, P_2, \ldots, P_N) також змінюється. Легко довести, що існують такі $P_{1}^{'}, P_{2}^{'}, \dots, P_{N}^{'}$ P_1', P_2', \ldots, P_N' в квадраті, що $LEN (P_{1}^{'}, P_{2}^{'}, \dots, P_{N}^{'})$ \mathrm{LEN}(P_1', P_2', \ldots, P_N') є мінімальною.

Знаючи початкові позиції $N$ точок, ваше завдання — знайти $N$ точок $P_{1}^{''}, P_{2}^{''}, \dots, P_{N}^{''}$ P_1'', P_2'', \ldots, P_N'' в квадраті такі, що $∣ P_{1} P_{1}^{''} ∣ + ∣ P_{2} P_{2}^{''} ∣ + \dots + ∣ P_{N} P_{N}^{''} ∣$ |P_1P_1''| + |P_2P_2''| + \ldots + |P_NP_N''| є мінімальним і $LEN (P_{1}^{''}, P_{2}^{''}, \dots, P_{N}^{''}) = LEN (P_{1}^{'}, P_{2}^{'}, \dots, P_{N}^{'})$ \mathrm{LEN}(P_1'', P_2'', \ldots, P_N'') = \mathrm{LEN}(P_1', P_2', \ldots, P_N'). Вам потрібно вивести значення $∣ P_{1} P_{1}^{''} ∣ + ∣ P_{2} P_{2}^{''} ∣ + \dots + ∣ P_{N} P_{N}^{''} ∣$ |P_1P_1''| + |P_2P_2''| + \ldots + |P_NP_N''|, де $∣ P_{i} P_{i}^{''} ∣$ |P_iP_i''| — це відстань між $P_{i}$ P_i та $P_{i}^{''}$ P_i''.

Наприклад, на Рисунку 1 показано початкову позицію $P_{1}$ P_1 і спосіб з'єднання для отримання $LEN (P_{1})$ \mathrm{LEN}(P_1). На Рисунку 2 показано позицію $P_{1}^{''}$ P_1'', яка знаходиться в центрі квадрата, і спосіб з'єднання для отримання $LEN (P_{1}^{''})$ \mathrm{LEN}(P_1''). Можна довести, що $LEN (P_{1}^{''}) = LEN (P_{1}^{'})$ \mathrm{LEN}(P_1'') = \mathrm{LEN}(P_1'); ваше завдання — вивести відстань між $P_{1}$ P_1 та $P_{1}^{''}$ P_1''.

Вхідні дані

Вхід складається з кількох тестових випадків. Для кожного тестового випадку перший рядок містить одне ціле число $N$ ( $1 \leq N \leq 100$ 1 \leq N \leq 100), кількість точок, і далі йдуть $N$ рядків, які задають координати кожної точки у наступному форматі:

$x y$

Тут $x$ та $y$ — дійсні числа в межах $[0, 1]$ .

Тестовий випадок з $N = 0$ N = 0 вказує на кінець введення і не повинен оброблятися.

Вихідні дані

Для кожного тестового випадку виведіть значення $∣ P_{1} P_{1}^{''} ∣ + ∣ P_{2} P_{2}^{''} ∣ + \dots + ∣ P_{N} P_{N}^{''} ∣$ |P_1P_1''| + |P_2P_2''| + \ldots + |P_NP_N''|. Значення повинно бути округлене до трьох знаків після коми.

Приклади

Приклад 1