Есть квадратная сетка размером до 4096x4096, некоторые клетки которой закрашены. Далее подается множество отрезков, заданных двумя точками. Необходимо узнать для каждого отрезка пересекает ли он хотя бы одну закрашенную клетку.
UPD2: Касание клетки не считается ее пересечением.
Ограничение на предпосчет 10 секунд.
Ограничение на память 2Гб.
UPD1: обновил решение
Мое решениеПостроим двумерный массив префикс сумм, в котором будем хранить количество закрашенных клеток. С его помощью мы сможем узнать количество закрашенных клеток внутри произвольного прямоугольника внутри сетки.
Для каждого отрезка выполним следующие шаги:
Для текущего отрезка определяем прямоугольник который он занимает.
Для данного прямоугольника вычисляем количество закрашенных в нем клеток. (при помощи префикс массива)
Посчитаем количество клеток которые пересекал бы отрезок, если бы он начинался не в середине клетки, а на пересечении клеток. Это количество равно длина прямоугольника + ширина прямоугольника — НОД(длина, ширина). Если же отрезок начинается в середине клетки, то это число может либо равно, либо больше посчитанного. (для дальнейшего сравнения можно этим пренебречь). Если это количество больше числа клеток посчитанных на 2 шаге, то значит отрезок пересекает хотя бы одну закрашенную клетку.
Если текущий прямоугольник состоит из одной клетки, то в данной области отрезок не пересекает закрашенные клетки.
Иначе делим данный прямоугольник пополам и для каждой половины повторяем со 2 шага.
Полный текст и комментарии »