Изменения

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

Convex hull trick

1 байт убрано, 20:53, 23 ноября 2016
Для чего нам нужна эта выпуклая оболочка прямых?
[[Файл:picture2convexhull.png]]
[[Файл:picture3convexhull.png]]
Действительно, пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то найдется такой отрезок <math>[x1;x2]</math>, что последняя(желтая) прямая при этих x-ах лежит ниже всех остальных и ее следует оставить в множестве. Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
==Детали реализации:==
186
правок

Навигация