Задача на с++

[Ganez]

Привет всем!

Не могу понять как сделать вот эту задачу:

Дан файл координат вершин ломаной линии на плоскости. Удалить из файла те вершины, которые находятся внутри выпуклой многоугольной оболочки, охватывающей ломаную линию.

может кто подскажет хотябы как делать?

[eoln]

Первое что приходит в голову - это в лоб для каждой точки брать две соседнии и на основе каждой из них строить каноническое уравнение прямой, затем для каждого уравнения проверять имеет ли данная прямая пересечения с другими сторонами {отрезками} (уравнение сторон также строятся по 2-м точкам и преобразуется в канонический вид). Отвечал на подобные вопросы с полным решением раза 3, правда на delphi, но главное идея.
C вас наработки - с нас помощь.

[Ganez]

спасибо, буду пробывать

[Ganez]

каноническое уравнение прямой

(x-x0)/m = (y-y0)/n

такое?


так x будет неизвестным? и игрик тоже?

и плюс откуда взять m и n

[eoln]

Не важен вид уравнения (каноническое, общее или ещё какое), главное чтобы работать было удобно. Берём последовательные пары точек и на их основе составляем уравнения прямых, например для точек X(x1, y1) и Y(x2, y2), имеем общее уравнение :
A12*x+B12*y+C12=0, где
A12=y1-y2
B12=x2-x1
C12=x1*y2-x2*y1

Теперь ищем точку пересечения этой прямой со всеми другими прямыми.
Например, найдём точку пересечения с прямой на точках (x5, y5) и (x6, y6), которое имеет уравнение
A56*x+B56*y+C56=0, где
A56=y5-y6
B56=x6-x5
C56=x5*y6-x6*y5

x0=(B12*C56-B56*C12)/(A12*B56-A56*B12)
y0=(C12*A56-C56*A12)/(A12*B56-A56*B12)
(x0, y0) - точка пересечения (следует предусмотреть существование этой точки, т.к. если прямые параллельны, то знаменатель обратится в ноль)
Итак, если точка существует (знаменатель не нулевой), то проверим принадлежит ли эта точка исходной стороне (применим свойство "лежать между")
Предположим что x1<=x2 иначе поменяем их местами (аналогично y1<=y2), тогда
ЕСЛИ (x5<=x0<=x6) и (y5<=y0<=y6) ТО данная пара точек нам неинтересна
Если после всех проверок "интерес" не потерян, то точки остаются в файле
Всё вышесказанное теперь применяем ко всем возможным комбинациям точек (перестановки не считаются). Смежные отрезки проверять не надо - это бесполезно, они всегда пересекаются