Есть квадратная сетка размера N * N, в каждой клетке которой записано магическое целое положительное число. Дистанция между двумя клетками равна сумме магических чисел в этих клетках и Евклидову расстоянию между этими клетками. Среди всех этих клеток R клеток покрашены в красный цвет, а G клеток покрашены в зеленый цвет. Для каждой зеленой клетки нужно найти такую красную, что не будет другой красной клетки дистанция до которой меньше.

512 <= N <= 4096 1 <= R + G <= N * N

Можно ли решить эту задачу быстрее чем O(G * R)? Если бы не было магического числа в клетках, то это была бы задача по [поиску ближайшего соседа] https://en.wikipedia.org/wiki/Nearest_neighbor_search).