Изменения
→Параллельный алгоритм
Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за <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>. 2) Если оказалось, что результаты разные, то мы берем <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 и есть верный ответ. Таким образом, у нас выходит примерно такой алгоритм - 1) Создаем функцию, которая находит касательную для точки из первого многоугольника на второй многоугольник. fun getFromPoint(K): '''int''' startAfter '''pfor''' i = 0...sqrt(n): '''int''' startCurrent = sqrt(n) * i '''int''' startNext = sqrt(n) * i + 1 '''int''' finishCurrent = sqrt(n) * i '''int''' finishNext = sqrt(n) * i + 1 '''boolean''' isStartBeforeAnswer = left_turn(startCurrent, K, startNext) > 0 '''boolean''' isFinishBeforeAnswer = left_turn(finishCurrent, K, finishNext) > 0 if (isStartBeforeAnswer != isFinishBeforeAnswer) startAfter = startCurrent '''pfor''' i = 0..sqrt(n): '''int''' start = i + startAfter '''int''' middle = i + startAfter + 1 '''int''' finish = i + startAfter + 2 if (left_turn(start, K, middle) != left_turn(middle, K, finish)) return middle Его <tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex> 2) Создадим функцию, которая находит касательную $AB$ между двумя многоугольниками (она будет сильно похожа на предыдущую функцию) {{Теорема|about=|statement=Если предыдущая точка $prev$ и следующая точка $next$ лежат по одну сторону (в нашем случае ниже) от касательной на второй многоугольник, то эта точка $x$ является точкой искомой касательной. Иначе - если $prev$ находится выше касательной, то мы дальше $A$, иначе - до $A$.|proof= Многоугольник выпуклый, значит, что если одна точка лежит на прямой, а две соседние по одну сторону от нее, значит, что эта прямая является касательной. Если $prev$ находится выше касательной, то это значит, что его касательная находится выше, значит, что AB тоже находится выше, а значит, что A находится раньше. Аналогично для обратного случая.}} Здесь у нас совершенно тот же код, просто мы вместо предиката левый поворот смотрим, где будет находиться предыдущая точка и следующая. <tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex> Итоговое время работы: <tex>work = n</tex>, <tex>span = \log{n}</tex>
