300iq's blog

By 300iq, history, 7 years ago, In Russian

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

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

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

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

  • Vote: I like it
  • +54
  • Vote: I do not like it