Изменения

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

Convex hull trick

2 байта добавлено, 00:20, 18 января 2017
Альтернативный подход
необходимо показать, что если есть 3 вектора a, b, c, расположенные как на рисунке 5 (т.е. <tex>[a-b, b-c] \leqslant 0</tex>, где <tex>[u, v]</tex> - модуль векторного произведения векторов <tex>u</tex> и <tex>v</tex>), то либо (a, u[i]) \leqslant (b, u[i]), либо (c, u[i]) \leqslant (b, u[i]).
Распишем условие того, что точка b не лежит на выпуклой оболочке векторов<tex> 0, a, b, c </tex> : <tex>[a-b, b-c] \leqslant 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) \leqslant (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u[i]) \leqslant (a, u[i]) \Leftrightarrow b_{x} + a[i]\cdotb_cdot b_{y} \leqslant c_{x} + a[i] \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) \leqslant a[i] \cdot (c_{y} - b_{y})</tex> и <tex>(b, u[i]) \leqslant (c, u[i]) \Leftrightarrow b_{x} + a[i] \cdot b_{y} \leqslant a_{x} + a[i] \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) \geqslant a[i] \cdot (b_{y} - a_{y})</tex>. Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) = a[i] \cdot (b_{y} - a_{y}) \cdot (b_{y} - c_{y}) \leqslant (a_{x} - b_{x}) \cdot (b_{y} - c_{y}) \leqslant (a_{y} - b_{y}) \cdot (b_{x} - c_{x}) \leqslant a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) \leqslant a[i] \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд.
Анонимный участник

Навигация