Есть квадратная сетка размера N * N, в каждой клетке которой записано магическое целое положительное число. Дистанция между двумя клетками равна сумме магических чисел в этих клетках и Евклидову расстоянию между этими клетками. Среди всех этих клеток R клеток покрашены в красный цвет, а G клеток покрашены в зеленый цвет. Для каждой зеленой клетки нужно найти такую красную, что не будет другой красной клетки дистанция до которой меньше.
512 <= N <= 4096
1 <= R + G <= N * N
Можно ли решить эту задачу быстрее чем O(G * R)? Если бы не было магического числа в клетках, то это была бы задача по поиску ближайшего соседа.
