Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Nearest neighbor search with addition weight

Revision en3, by xagofes, 2019-02-24 00:56:48

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English xagofes 2019-02-24 01:00:07 2
en3 English xagofes 2019-02-24 00:56:48 0 (published)
ru4 Russian xagofes 2019-02-24 00:56:21 0 (опубликовано)
ru3 Russian xagofes 2019-02-24 00:56:05 2 Мелкая правка: ' <= 4096\n1 <= R +' -> ' <= 4096\n\n1 <= R +'
en2 English xagofes 2019-02-24 00:55:48 2 Tiny change: ' <= 4096\n1 <= R +' -> ' <= 4096\n\n1 <= R +'
en1 English xagofes 2019-02-24 00:55:08 715 Initial revision for English translation (saved to drafts)
ru2 Russian xagofes 2019-02-24 00:45:07 2 Мелкая правка: 'го соседа] https://en' -> 'го соседа](https://en'
ru1 Russian xagofes 2019-02-24 00:44:31 734 Первая редакция (сохранено в черновиках)