170
правок
Изменения
м
Нет описания правки
[[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|Найдём выпуклую оболочку]] исходного множества и получим более простую задачу: найти две наиболее удалённые вершины в выпуклом многоугольнике. Сделать это можно за линейное время с помощью метода, который называется '''вращающиеся калиперы''' (англ. ''rotating calipers'').
''Обоснование: Пусть диаметр с одной стороны содержит точку, которая не принадлежит выпуклой оболочке. Тогда продлим диаметр в эту сторону до пересечения с выпуклой оболочкой. Очевидно, он станет длиннее. А потом заметим, что диаметр станет еще больше, если сдвинуть его к одному из концов ребра, в которое мы уперлись. Конец.''
== Постановка задачи ==
