Ближайшая точка от текущей точки

Question

Ввод:

• 2-мерное пространство размером MxN.

• K точек (целая пара)в этом 2 тусклом пространстве.

Вывод:

Точка xj, yj из множества K точек, таких что dist (i, j)в минимуме, где xi, yi - текущая точка.

dist (i, j) : среднеквадратичное расстояние

Дано K << M * N, K~ M, K ~ N, M ~ N </p>

Ожидаемая сложность по времени:

• O (M * N) для каждого запроса явно недостаточно.
• O (K) для каждого запроса также недостаточно.
• Все, что лучше этого, будет приемлемым.