тема Графы Опции

[Vampire]

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

[Vampire]

Эм.. Сделал я следующее: ввел список из ~7 точек ( простеньких в последовательности: 1,1, 2,2, 3,3, 5,5, 6,4 ну там и т.д.) и смотрю по трем точкам (начальные: 1,1, 2,2, 3,3): если например средняя принадлежит прямой, на которой расположены остальные две, то тогда отметить ее.. Т.е. просто проверяю какие точки лежат на прямой с другими и помечаю их для НЕ вывода. А потом просто вывожу список не отмеченных точек. Знаю что не правильно в корне и все такое, но это все что я смог придуать... Будем надеятся на недалекость моего препода... Хотя хотел для себя решить таки эту задачу...
Спасибо за помощь.. Хотя если не сдам, придется таки решать как надо..