День 11. Геометрия многоугольников.

1. [Сергей Копелиович] Выпуклая оболочка
1. Заворачивание подарка за O(nk)
2. Грехем за O(nlogn), Эндрю за O(nlogn) − сортировка по X
3. Quick-Hull


2. [Олег Давыдов] Выпуклый многоугольник и два указателя
1. Две самые дальние точки среди n данных
2. Самый большой треугольник, построенный на n данных точках
3. Даны m прямых и выпуклый n-угольник, для каждой прямой узнать, пересекает ли она многоугольник
4. Общая касательная к двум выпуклым непересекающимся многоугольникам


3. [Игорь Лабутин] Выпуклый многоугольник и логарифм
1. Внутри ли точка?
2. Самая дальняя точка по направлению (A_i, B_i) среди данных n точек (опорная прямая)
3. Пересечение многоугольника и прямой
4. Касательная к многоугольнику
5. Расстояние от точки до многоугольника


4. [Сергей Копелиович] Два выпуклых многоугольников − два логарифма
1. Расстояние между
2. Общая касательная


5. [Сергей Копелиович] Задачи
1. Дан массив точек. Запрос на отрезке [l_i, r_i]: "самая дальняя по направлению (a_i, b_i)"
2. Добавляются и удаляются точки. Проверять, внутри ли выпуклой оболочки точка-запрос.