Математика:
Вычислительная геометрия:
Разное.

На плоскости заданы n отрезков координатами концевых точек.
Концы отрезков задаются двумя парами координат (x₁[i],y₁[i]), (x₂[i],y₂[i]), 1<=i<=n (концы принадлежат отрезку).
Необходимо найти прямую, имеющую общие точки с максимальным числом отрезков, и напечатать в порядке возрастания номера тех отрезков, которые эта прямая пересекает.

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

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

Вверх по странице, к оглавлению и навигации.