1 Тема от xenobit

  • xenobit
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-05-14
  • Сообщений: 3

Тема: Прямая пересекающая максимальное число окружностей

На плоскости даны окружности, максимум 200 штук. Заданы координатами (целое  от -32768 до 32767) и радиусом (натуральное число от 1 до 32767). В ответ нужно вывести максимальное количество окружностей которое можно пересечь одной прямой.

Помогите, пожалуйста, с задачей; не знаю даже с какой стороны подойти.

2 Ответ от KADR

  • KADR
  • Участник
  • Неактивен
  • Откуда: Киев
  • Зарегистрирован: 2009-06-25
  • Сообщений: 231

Re: Прямая пересекающая максимальное число окружностей

Очевидно, что прямая должна касаться как минимум двух окружностей (иначе ее можно сдвинуть или развернуть так, чтобы она касалась 2 окружностей, не изменив общее количество окружностей, имеющих с ней общие точки). Затем переберем все пары окружностей, для каждой пары построим 4 общих касательных и для каждой касательной за O(N) проверим сколько окружностей она пересекает. Сложность O(N^3).