Изменения

Перейти к: навигация, поиск

Диаметр множества точек (вращающиеся калиперы)

122 байта добавлено, 15:57, 8 января 2014
м
Нет описания правки
Есть множество точек на плоскости. Нужно найти две самые удалённые из них.
[[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|Найдём выпуклую оболочку ]] исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
== Постановка задачи ==
64
правки

Навигация