Изменения

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

Convex hull trick

287 байт добавлено, 01:29, 18 января 2017
Нет описания правки
Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = a[i]</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< a[i] \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.
==См. также==
1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull
2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование
Анонимный участник

Навигация