Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Ломаная
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
На плоскости задана незамкнутая ломаная. Никакие две ее вершины не совпадают. Требуется найти прямую, пересекающую максимальное количество последовательных звеньев. Пересечение звена - это пересечение его ровно в одной внутренней точке.
N - количество вершин ломаной (2 ? N ? 2000)
в вершинах пересечние считается?
Можно просто перебирать отрезок с которого начнём искать ответ, далее начинаем бежать с этого отрезка постепенно сужая отрезок видимости,как только он стал невидим,значит предыдущий отрезок с отрезком с которого начинали будет некоторый ответ. И так далее. Сложность N^2...
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Ломаная