Sweep Line (Silver-Gold) Intro

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:

http://www.usaco.org/index.php?page=viewproblem2&cpid=567

https://cses.fi/problemset/task/1619

http://www.usaco.org/index.php?page=viewproblem2&cpid=786

http://www.usaco.org/index.php?page=viewproblem2&cpid=344

2D Sweep Line (Plane Sweep):

http://www.usaco.org/index.php?page=viewproblem2&cpid=1040

http://www.usaco.org/index.php?page=viewproblem2&cpid=619

http://www.usaco.org/index.php?page=viewproblem2&cpid=227

http://www.usaco.org/index.php?page=viewproblem2&cpid=645

http://www.usaco.org/index.php?page=viewproblem2&cpid=943

Written Resources:

https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/ https://www.topcoder.com/community/competitive-programming/tutorials/line-sweep-algorithms/ https://codeforces.com/blog/entry/58747 (implementation views sweep line as similar to D & C) https://codeforces.com/blog/entry/20377 https://courses.csail.mit.edu/6.006/spring11/lectures/lec24.pdf https://en.wikipedia.org/wiki/Sweep_line_algorithm

https://cses.fi/book/book.pdf#page=173

http://www.usaco.org/current/data/sol_cowjump_silver_open19.html (good USACO editorial demonstration)

https://github.com/Aryansh-S/USACO/tree/master/algo%20%26%20ds/SweepLine

Video Tutorials:

https://www.youtube.com/watch?v=bEEbslngvxI

https://www.youtube.com/playlist?list=PLubYOWSl9mItBLmB2WiFU0A_WINUSLtGH