Квадрати#358

Квадрати (Розбір)

Обмеження маленькі (), тому вистачає перебору за \mathcal{O}(N^4) — це щонайбільше кілька мільйонів операцій. Головне — не забути про повернуті квадрати: сторони не зобов'язані бути паралельними осям.

Зручний спосіб перебору — по стороні. Візьмемо дві точки A = (x_1, y_1) та B = (x_2, y_2) і вважатимемо відрізок стороною квадрата. Позначимо dx = x_2 - x_1, dy = y_2 - y_1. Тоді дві інші вершини отримуються поворотом вектора (dx, dy) на :

C = (x_2 - dy,\; y_2 + dx), \qquad D = (x_1 - dy,\; y_1 + dx).

Перевіряємо, що і не виходять за межі сітки, і що всі чотири точки мають однаковий колір. Якщо так — знайдено квадрат.

Залишається не порахувати одне й те саме кілька разів. Кожен квадрат має чотири сторони, і кожна з них колись стане парою , тому кожен квадрат буде знайдено рівно чотири рази. Тому наприкінці поділіть підсумок на . (Другий поворот, на , розглядати не потрібно: він дає той самий квадрат, тільки знайдений з іншого боку.)

Відповідь може перевищувати межі 32-бітного типу, тому накопичуйте її у 64-бітному.