Разделяй и властвуй. Задачи на прямой

Пятница, 30 сентября 2016
Таймс, 4 этаж

Описание

Для более полного понимания происходящего можно (но не обязательно!) пройти 5.2.Умножение чисел

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