Решение задачи 10.
Строим выпуклую оболочку данного множества точек - т.е. такой выпуклый многоугольник, вершинами которого являются некоторые из этих N точек (возможно, не все), что через какое бы ребро этого многоугольника мы ни провели прямую, все N точек исходного множества будут лежать по одну сторону от этой прямой и на ней (определение местоположения точек относительно прямой см. задачу 6).
Из произвольной точки a1 множества A из N точек мы можем провести не более N-1 - го отрезка так, чтобы и вторая концевая точка этого отрезка была из множества A. Берем тот отрезок [a1,a2], для которого все точки множества A лежат по одну сторону от прямой, проходящей через этот отрезок (если любой отрезок не удовлетворяет этому условию, то берем другое a1; с самого начала лучше всего взять в качестве a1 точку с максимальной абсциссой, а если таких несколько, то среди них берем точку с максимальной ординатой -- это гарантирует, что a1 принадлежит искомому контуру выпуклого многоугольника). Для точки a2 ищем точку a3<>a1 так, чтобы все множество A лежало по одну сторону от прямой, определяемой отрезком [a2,a3], ..., для точки ai ищем ai+1<>ai-1 так, чтобы A лежало по одну сторону от [ai,ai+1)], и т.д., до тех пор, пока очередной точкой ai+1 не станет ai - мы замкнули контур, и нашли выпуклую оболочку. Все точки множества A, не лежащие на контуре, лежат внутри выпуклой оболочки.
|
