Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 28.04.2009, 19:03
Новичок

Отправить личное сообщение для alienlab Посмотреть профиль Найти все сообщения от alienlab
 
Регистрация: 28.04.2009
Сообщений: 1

Нахождение фигуры максимальной площади
Доброго времени суток, уважаемые жители форума и его гости!

Обращаюсь к вам с просьбой о помощи в составлении (или нахождении) алгоритма решения следующей, достаточно тривиальной для человека задачи.

В дискретном N x N пространстве есть множество точек. Две точки являются соседними, если они находятся на расстоянии не более "корень из 2" (т.е. по горизонтали или диагонали). Точки бывают двух видов: "свои" и "чужие".

Можно ли составить замкнутую "ломаную" (линию из прямых линий), построенную по "своим" соседним точкам так, чтобы внутри нее оказалась хотя бы одна "чужая" точка? Если да, то найти такую линию, чтобы при этом площадь фигуры (ломаная + ее внутренность) была максимальной.

Пример:


Заранее благодарен!
  #2  
Старый 28.04.2009, 20:14
Новичок

Отправить личное сообщение для e-maxx Посмотреть профиль Найти все сообщения от e-maxx
 
Регистрация: 14.03.2009
Сообщений: 24

Я бы построил по этим точкам планарный граф и нашёл бы все его внешние грани. Для каждой грани надо проверить, есть ли внутри неё красная точка, и среди всех таких выбрать наибольшую по площади. Т.к. мы искали ответ среди внешних граней, большего полигона быть не могло.

В данном примере будет две внешних грани: нарисованная, но с присоединённой зелёной точкой наверху (она присоединится с "хвостом" нулевой площади, но ответ он не ухудшает), ну и грань, состоящая из единственной оставшейся зелёной точки.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычисление площади произвольной фигуры методом Монте-Карло Skinny Вычислительная геометрия 4 05.10.2010 13:51
поиск цикла максимальной длинны в графе гость Графы 2 21.12.2008 04:00
Вычисление площади пересечения двух прямоугольников mark_tyler Вычислительная геометрия 1 31.08.2008 04:10
Нахождение прямоугольника максимальной площади гость Задачи 13 15.05.2008 20:49
минимальное стягивающее дерево по критерию максимальной живучести ТРСО andrew_zol Графы 0 21.06.2007 03:08