Моё решение занимает ~250 строк кода на С++. Оно использует цикл по двум указателям (видимо, так же, как и у Вас), внутри которого выполняется тернарный поиск. И всё.

Писал я его давно, так что с лёту более подробно не расскажу. Если Вам интересно такое моё решение, я освежу его в памяти и попытаюсь изложить здесь.

Можно рассмотреть точки на периметре с каким-нибудь интервалом. Для каждой из этих точек бинпоиском найти сторону многоугольника, где лежит точка P такая, что отрезок, соединяющий P с выбранной точкой делит многоугольник пополам. Потом ещё одним бинпоиском найти эту точку P на найденной стороне. И из всех таких отрезков выбрать отрезок минимальной длины. Правда, пришлось долго выбирать точность, чтобы криво написанное решение на джаве зашло.

прошу прощения,написал 1048,промазал.(

Сейчас написал, после убирания ненужных строк из шаблона получилось меньше 100 строк абсолютно не парясь. Зашло с плюса даже без отладки, я аж сам удивился :) Вот код.

Решение: перебираем сторону, на которой лежит одна точка разреза. Положение точки на этой стороне ищем тернарником. Вторую точку находим линейным проходом по всем остальным сторонам. На каждом шаге мы можем либо откусить следующий треугольник целиком, либо отрезать некоторую часть и остановиться. Во втором случае место, где нужно резать, определяется по тривиальной линейной формуле. В итоге получается O(N²logN).

Я решал так — переберем сторону многоугольника, пусть это отрезок (P1, P2), построим (P1, T1), (P2,T2) — эти отрезки делят весь многоугольник на две части, теперь елси рассмотреть все точки многоугольника которые лежат "между" T1 и T2, получим набор отрезков вида (T1, P_i), (P_i, P_i+1), ... , (P_j, T2), если зафиксировать какой-то из этих отрезков, и выбрать на нем любую точку — R, и (R, E) — делит многоугольник попалам, E всегда попадет на отрезок (P1, P2), значит делаем тернарку по каждому отрезку из (T1, P_i), (P_i, P_i+1), ... , (P_j, T2). Получилось 200+ строк кода , и сложность O(N^3 logP)