xagofes's blog

By xagofes, history, 9 months ago, translation, In English,

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.

Read more »

  • Vote: I like it
  • +9
  • Vote: I do not like it

By xagofes, history, 15 months ago, In Russian,

Есть квадратная сетка размером до 4096x4096, некоторые клетки которой закрашены. Далее подается множество отрезков, заданных двумя точками. Необходимо узнать для каждого отрезка пересекает ли он хотя бы одну закрашенную клетку.

UPD2: Касание клетки не считается ее пересечением.

Ограничение на предпосчет 10 секунд.

Ограничение на память 2Гб.

UPD1: обновил решение

Мое решение

Read more »

  • Vote: I like it
  • +8
  • Vote: I do not like it