Автор: | Павло Ціцей |
Підготовка задачі: | Павло Ціцей |
Розбір: | Павло Ціцей |
Блок : x_i^2+y_i^2\le 18 для всіх :
Ми можемо замінити на , якщо x^2+y^2=a^2+b^2, що означає, що ми можемо замінити (-x, y) на та на , тому ми можемо зробити всі координати у вхідних даних типу 0\le x\le y і згрупувати їх разом. Таким чином, у нас є 10 типів таких груп (якщо не враховувати ). Отже, ми можемо вирішити це як третій блок.
Блок : n=1:
Зверніть увагу, що відстань від до дорівнює \sqrt{x^2+y^2}, тому якщо ми змінюємо на , де x^2+y^2=a^2+b^2, тоді відстань не змінюється. Отже, відповідь це сума квадратів чисел, помножена на 4.
Блок : n\le 10:
Ми можемо спробувати кожну перестановку точок, яка визначає шлях, яким ми йдемо, а перший і останній елемент будуть . Загальна складність буде .
Блок : без додаткових обмежень:
Ми можемо змінити координати кожної точки з на (0, \sqrt{x^2+y^2}). Тоді відповідь буде максимальним з цих точок, помноженим на 2 (оскільки нам потрібно повернутися).