Будемо розглядати точки в задачі як клітинки прямокутника зі сторонами та , а координати це індекси клітинки в такій матриці.
Розглянемо конструкцію у випадку коли та одночасно парні. У такій ситуації ми можемо розрізати прямокутник на 4 менші однакові прямокутники, розрізами посередині рядків та стовпців. Тепер ми можемо співставити лівий верхній прямокутник із нижнім правим, та два інші. Тобто будемо робити по 2 клітинки кожного кольору. Детальніше співставлення можна подивитись на рисунку 1 нижче.
Відповідь для = 4, = 6
Якщо ж одне з чисел та є парним, а інше непарне, то розрізати на прямокутники треба дещо інакше. Наприклад, коли кількість рядків непарна, то ми можемо ліву частину центрального рядка долучити до лівого верхнього прямокутника і праву частину до правого нижнього прямокутника. Детальніше співставлення можна подивитись на рисунку 2 нижче.
Відповідь для = 5, = 6
У випадку коли обидва числа непарні, то ми зробимо подібний процес зі стовпцем. Проте станеться така ситуація, що центральну клітинку покривають і лівий верхній, і нижній правий прямокутники. То пофарбуємо ліву верхню клітинку, праву нижню клітинку і центральну в один колір. Детальніше співставлення можна подивитись на рисунку 3 нижче.
Відповідь для = 5, = 7
В усіх випадках така конструкція дає найкращу можливу відповідь, оскільки для кожної з центральних клітинок неможливо отримати відстань кращу за \lfloor \frac{n}{2} \rfloor ^2 + \lfloor \frac{m}{2} \rfloor ^2.
Складність O(n \cdot m).