На контесте в ЛКШ зашел следующий алгоритм:

Шафлим полуплоскости, перебираем пару, находим точку пересечения, бежим по всем полуплоскостям, когда встречаем полуплоскость в которой эта точка не лежит -> break; Дальше строим выпуклую оболочку всех точек, которые лежат во всех полуплоскостях.

Полуплоскостей было <= 2000.

Слабые тесты или матожидание времени работы быстрее куба?