Метод разделяй и властвуй, задачи на прямой

Четверг, 01 октября 2015

Таймс, ауд. 404

Две ближайшие точки в 2D, в 3D за $O(n \log n)$
Экстремальные точки на прямой (например, минимизируем сумму расстояний до остальных, сумму квадратов расстояний до остальных)
Подотрезок максимальной суммы