Есть у меня координаты точек (N штук, порядка 10000). Если соединить эти точки, получается ломанная. Необходимо соединить две любых точки, чтобы получилась фигура, с максимальной площадью. Помимо этого, нельзя чтобы линия между двумя точками пересекала ломанную.
Получется примерно вот такая картинка:
Есть идея перебирать напрямую пары точек (1,3), (1,4), ..., (1,N); (2,4), (2,5), ..., (2,N); и после проверять пересечение линии с кажой из N частей ломанной, но это получиться по меньшей мере не рационально.
Есть ли какие нибудь другие алгоритмы нахождения линии, не пересекающей ни одну из частей кривой?
). То есть, для точки X+у+1, если ее Y координата не "экстремальнее" точек {X+2.. X+у}, то отрезок пересечется...
