Здравствуйте Painkiller, Вы писали:

P>Здравствуйте Young, Вы писали:

Y>> Ищем углы прямоугольников — точки у которых соседи слева и сверху или слева и снизу имеют другой цвет. Проводи через них прямые и получаем набор прямоугольников. Не минимальный но всеже — потом решаем задачу их объединения — тут уже много вариантов. Например — находим центры прямоугольников — строим граф — соединяем только те вершины которые лежать на одной вертикали или горизонтали. И ищем наибольший цикл (или просто циклы) — находим удаляем. И объединяем те прямоугольники центры которых входят в цикл. И так далее. потом соединяем оставщиеся прямые.

P>Что-то я нынче туго соображаю :( Можно для начала немного поподробнее — какие точки выбираются, какие прямые проводятся. Лучше всего — на примерах


Попробую на примерах.

И так есть многоугольник.




Отмеченные точки находиться следующим образом
Для точки X,Y
If (Point[X-1,Y].Color != Point[X,Y].Color) and ((Point[X,Y-1].Color != Point[X,Y].Color) or (Point[X,Y+1].Color != Point[X,Y].Color))


Потом проводим горизонтальные (или вертикальные) прямые через эти точки – они разбивают многоугольник на прямоугольники. Ну а потом объединяем их методом который я предложил или другим.





Y>>P.S. Пмниться была эта задачка на одном из туров Московской олимпиады.

P>Вот это интересно. На какой именно и в каком году? Где нибудь в сети можно про это что-нибудь обнаружить?

Примерно лет пять-шесть назад. Я почему как раз и вспомнил – но в сети не нашел.



С Уважением Андрей.......