:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Геометрия » Разное » Найти прямую, пересекающую макс. число отрезков
На правах рекламы
запасные части для дробилок extec.
За небольшую оплату intel nuc kit недорого, со скидками.
На нашем сайте песок истра для вас со скидками. Качественно.
  Найти прямую, имеющую общие точки с макс. числом заданных отрезков и напечатать в порядке возрастания номера отрезков, которые она пересекает



Один из возможных методов решения. Предположим, мы нашли такую прямую. Будем сдвигать ее в направлении, перпендикулярном этой прямой (параллельный перенос) до тех пор, пока она не пересечет какую-нибудь из концевых точек отрезка. За счет поворота прямой вокруг этой точки мы можем добиться того, что прямая будет проходить через 2 концевые точки отрезков и не перестанет быть решением задачи.

Следовательно, мы должны рассмотреть прямые, проходящие через все возможные комбинации пар концевых точек отрезков. Всего надо проверить (2*N-1)+(2*N-2)+...+1=N*(2*N-1) линий и для каждой из них найти число пересечений с отрезками. Та прямая, у которой это число максимальное, и есть искомая.