Архив форумов ЦИТФорума

[P111gr1m]

Здравствуйте. Подскажите алгоритм решения этой задачки или где можно почитать на тему.
На плоскости заданы n точек. Соеденить их непересекающимися отрезками таким образом,чтобы каждая область внутри выпуклой оболочки этого множества точек являлась треугольником

[next]

самый тупой способ:
1) берем точку
2) проводим из нее отрезки во все остальные точки
3) если есть еще точки, возвращаемся к шагу 1
4) исключаем все пересекающиеся отрезки

примеры хранения структуры точек (ака графа) берем из учебника по C++, а уравнение общей точки двух отрезков берем из учебника геометрии младших классов.