Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

10:08p

Как быстро вычислить площадь? Тетрадный лист имеет размеры N на N единичных клеточек. На этом листе нарисована какая-то односвязная область, составленная из целых клеток. Например, такая:

Граница этой области может быть сложной, но не очень: её длина L = O(N)
Площадь области в общем случае S = O(N^2)
Алгоритм получает на вход границу этой области в виде массива из L точек, соответствующего замкнутому маршруту обхода этой области (напр, по часовой стрелке).
Памяти много.
Можно ли вычислить S быстрее, чем за квадратичное время?