Московская олимпиада по информатике - 2005: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 247:
==Задача D. Восстанови многоугольник==
''Автор задачи и разбора – В.М.Гуровиц''[[Изображение:moi_06_1_D1.gif|frame|Рис. 1]]
Опишем алгоритм восстановления многоугольника по числам в клетках; из этого алгоритма в частности будет следовать, что решение всегда единственное.
Рассмотрим пример, изображенный на рис. 1.
Будем восстанавливать границы многоугольника, двигаясь сверху вниз. Начнем с верхней строки. Посмотрим на одну из единиц, стоящую в верхней строке. Верхняя сторона этой клетки не может принадлежать границе многоугольника, поскольку, по условию, многоугольник лежит ''внутри ''листа бумаги. Боковые стороны этой клетки тоже не могут лежать на границе многоугольника, поскольку их концы выходят на границу листа. Следовательно, многоугольнику принадлежит нижняя сторона клетки, см. рис. 2.[[Изображение:moi_06_1_D2.gif|frame|Рис. 2]]
| |||