2
1

На плоскости заданы $%n$% белых и $%m$% черных точек. Постройте $%O(n+m)$%-алгоритм, который находит, если это возможно, прямую, отделяющую каждую белую точку от каждой черной.

задан 23 Май '16 22:24

изменен 24 Май '16 1:29

Помогите, пожалуйста, с решением. Подскажите, с чего начать.

(24 Май '16 1:11) Uchenitsa
10|600 символов нужно символов осталось
2

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

ссылка

отвечен 24 Май '16 12:03

@falcao, спасибо!

(24 Май '16 18:36) Uchenitsa
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×242
×154
×50

задан
23 Май '16 22:24

показан
448 раз

обновлен
24 Май '16 18:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru