как использовать концепцию выпуклой оболочки для решения этой проблемы

Я решал эту задачу SPOJ, в которой используется концепция выпуклой оболочки.

Перейдите по приведенной выше ссылке, чтобы полностью понять вопрос

Если немного изменить эту задачу и дать нам точку, скажем A(x,y), и попросить найти максимальное количество заборов только вокруг этой конкретной точки.

Мой подход

(Поправьте меня, если я ошибаюсь)

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

2.Найдите количество оболочек, внутри которых лежит точка A.

Пожалуйста, помогите мне, как подойти к этой проблеме??

P.S.: - Я не смог найти подобной проблемы, чтобы проверить свой подход. Если вы обнаружите аналогичную проблему, прикрепите ее ниже.

Спасибо.


c++ algorithm computational-geometry convex-hull
person Shyam    schedule 07.06.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ваш подход работает нормально. Как вашу проблему, так и проблему SPOJ можно рассматривать рекурсивно следующим образом.

Учитывая набор полюсов:

  1. определить наилучшее внешнее ограждение
  2. Решите проблему еще раз со столбами внутри этого забора.

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

Таким образом, на шаге (1) выпуклая оболочка доступных полюсов всегда является допустимым выбором, поскольку набор полюсов внутри нее представляет собой надмножество полюсов, оставшихся после любого другого выбора. Для вашей проблемы он также будет заключать в себе точку A, если есть какой-либо другой выбор.

person Matt Timmermans    schedule 07.06.2020
comment
Спасибо за ответы . Было бы здорово, если бы вы могли сослаться на некоторые проблемы, в которых используется вышеуказанная концепция. - person Shyam; 07.06.2020