Вход


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

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

  


Номер 11


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


Задача 11. На решетке размера m*n заданы k точек своими координатами. Необходимо определить, можно ли построить выпуклый многоугольник такой, что каждая точка принадлежит некоторой стороне.

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


Решение задачи 11. Предположим, что мы построили искомый выпуклый многоугольник. Если какая-то точка a (из данного в условии набора S, состоящего из k точек) лежит на стороне многоугольника, то мы считаем ее новой вершиной этого многоугольника. Мы можем считать, что все вершины данного многоугольника есть точки набора S (если это не так, и между двумя точками a и b набора S лежит одна или несколько "посторонних" вершин, то мы можем их отбросить и считать, что a и b - две последовательные вершины контура. Многоугольник при этом у нас остается выпуклым (отрезок [a,b] делит фигуру на два выпуклых многоугольника), а так как на контуре между a и b не лежало ни одной точки из S, то многоугольник все еще удовлетворяет требованиям задачи). Итак, в качестве решения задачи мы получили выпуклую оболочку множества S (о построении ее см. задачу 10). Если построенная выпуклая оболочка такова, что каждая точка S является ее вершиной (или лежит на стороне), то задача решена, иначе решения не существует.

Назад



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

  


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