There is a grid of size N * N. Each cell of the grid contains a magic positive integer. The distance between two cells is equal to the sum of the magic numbers in these cells and the Euclidean distance between these cells. Among all these cells, the R cells are painted red and the G cells are painted green. For each green cell, we need to find such a red one that there is no other red cell, the distance to which is less.

512 <= N <= 4096

1 <= R + G <= N * N

Is it possible to make it better than O(G * R)?

If there were no magic number in the cells, it would be Nearest neighbor search problem.