Привет, **Codeforces**!↵
Заинтересовал вопрос о проверке пересекает ли прямая данный выпуклый многоугольник (прямых до 10^5, вершин в многоугольнике тоже до 10^5), все запросы в оффлайне. Долго искал в интернете, но ничего не нашёл, и в голову лезет только тупое решение за квадрат. Подскажите, пожалуйста, идею.
Заинтересовал вопрос о проверке пересекает ли прямая данный выпуклый многоугольник (прямых до 10^5, вершин в многоугольнике тоже до 10^5), все запросы в оффлайне. Долго искал в интернете, но ничего не нашёл, и в голову лезет только тупое решение за квадрат. Подскажите, пожалуйста, идею.
