Задача Fourpoints.
У цьому році після успішного завершення Турніру Чемпіонів ініціативна група вирішила провести квест. Було прийняте рішення обладнати чотири станції і тепер потрібно визначити, де необхідно розташувати координаційний центр квесту. Єдиною вимогою для його розміщення є виконання такої умови: сумарна відстань від координаційного центра до кожної станції повинна бути мінімальною.
Технічні умови
Програма Fourpoints спочатку зчитує з клавіатури (стандартного пристрою введення) єдине натуральне число N(1≤N≤50000) – кількість наборів, що тестуються. Далі йдуть N рядків, кожен з яких містить координати чотирьох попарно різних точок, де розміщено станції. Усі координати – цілі числа, що не перевищують за абсолютною величиною 10000.
Програма виводить на екран (стандартний пристрій виведення) N рядків, які містять мінімальну сумарну відстань від координаційного центра до вказаних чотирьох станцій. Відповідь буде зарахована, якщо буде відрізнятися від правильної не більш ніж 10-5.
Приклади
|
Введення |
Виведення |
|
2 0 0 0 1 0 2 0 3 0 0 1 1 0 1 1 0 |