Привет, Codeforces! Кто-нибудь знает как написать до сверху так, чтобы оно потребляло 2n памяти? В интернете нашёл лишь реализации за 4n.

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