Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Геометрия >> Номер 10

[Назад]    [Содержание ]    [Вперед]

  


Номер 10


  Условие: Номер 10


Задача 10. N точек на плоскости заданы своими координатами. Найти такой минимальный по площади выпуклый многоугольник, что все N точек лежат либо внутри этого многоугольника, либо на его границе (такой выпуклый многоугольник называется выпуклой оболочкой).

  Решение задачи: Номер 10


Решение задачи 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, не лежащие на контуре, лежат внутри выпуклой оболочки.

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017