Sweep Line (Silver-Gold) Intro
Last updated
Was this helpful?
Last updated
Was this helpful?
Sweep line is one of the most useful algorithms to have in your competitive programming toolkit. Unfortunately, not very many good sources exist to learn the approach. Of the ones that do exist, many discuss the approach superficially without examples and concrete implementation in code.
This guide aspires to change that in two parts:
1D Sweep Line
2D Sweep Line (Plane Sweep)
A third part, if created, would discuss more advanced applications, such as sweep line in conjunction with other algorithms, or rotating calipers.
Exposition will be based on the following list of problems (resources inspiring the series are also included afterward); you may wish to go through them on your own time before reading the series itself:
1D Sweep Line:
2D Sweep Line (Plane Sweep):
Written Resources:
Video Tutorials:
(implementation views sweep line as similar to D & C)
(good USACO editorial demonstration)