Задача 9.
На плоскости заданы n отрезков координатами концевых точек. Концы отрезков задаются двумя парами координат (x1[i],y1[i]), (x2[i],y2[i]), 1<=i<=n (концы принадлежат отрезку).
Необходимо найти прямую, имеющую общие точки с максимальным числом отрезков, и напечатать в порядке возрастания номера тех отрезков, которые эта прямая пересекает.
|
Решение задачи 9.
Один из возможных методов решения. Предположим, мы нашли такую прямую. Будем сдвигать ее в направлении, перпендикулярном этой прямой (параллельный перенос) до тех пор, пока она не пересечет какую-нибудь из концевых точек отрезка. За счет поворота прямой вокруг этой точки мы можем добиться того, что прямая будет проходить через 2 концевые точки отрезков и не перестанет быть решением задачи.
Следовательно, мы должны рассмотреть прямые, проходящие через все возможные комбинации пар концевых точек отрезков. Всего надо проверить (2*N-1)+(2*N-2)+...+1=N*(2*N-1) линий и для каждой из них найти число пересечений с отрезками. Та прямая, у которой это число максимальное, и есть искомая.
При решении возникает подзадача.
Определить, пересекается ли прямая ax+b=y и отрезок с концами (x1,y1), (x2,y2).
Решение ее - см. Задача 6.
|
