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



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

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