Краківські пам'ятки#405

Краківські пам'ятки (Розбір)

Автор:

Павло Ціцей

Підготовка задачі:

Павло Ціцей

Розбір:

Павло Ціцей

Блок : 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 (оскільки нам потрібно повернутися).