Изменения

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 get(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 мы запускаем pfor по <tex>\sqrt{n}</tex> точек равных <tex>i \cdot \sqrt{n}</tex>