91
правка
Изменения
Нет описания правки
Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB.
Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O(nlogn\log(n))</tex>
Прежде чем решать эту задачу, давайте решим такую задачу:
Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже.
Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от <tex>0 </tex> до <tex>1</tex>. Похоже на задачу бинарного поиска. Давайте опишем шаги:
'''int''' l = 0, r = n - 2
r = m
Нахождение касательной из точки на многоугольник работает за <tex>O(\log(n))</tex>
{{Задача
Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <tex>O(log^2(n))</tex>, а можно сделать его за <tex>work = O(n)</tex>, при этом уменьшив span
Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на <tex>\sqrt(n)</tex> частей.
Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на <tex>\sqrt(n)</tex> различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:
1) Берем <tex>\sqrt{n}</tex>, <tex>2\sqrt{n}</tex>, <tex>3\sqrt{n}</tex>, ..., <tex>\sqrt{n}\sqrt{n}</tex> и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает <tex>0 </tex> или <tex>1 </tex> - левее или правее они результата. Каждый результат считает за себя <tex>k\sqrt{n}</tex> и за соседа <tex>(k + 1)\sqrt{n}</tex>. Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.
