Sweep Line
Authors: Benjamin Qi, Andi Qu
Prerequisites
Introduction to line sweep.
Imagine you have a vertical line that "sweeps" the plane from left to right. That's the main idea behind the sweep line.
You might be thinking "wait - isn't keeping track of the sweep line at all possible positions super inefficient?" And you'd be correct. However, we don't actually need to keep track of the sweep line at all possible positions - only at the "critical" positions (e.g. points and intersections).
This section is not complete.
should the reader already be familiar with the 1D case (union of intervals on number line?) never explicitly mentioned in module
| Resources | |||
|---|---|---|---|
| CPH | |||
| TC | |||
Closest Pair
Focus Problem – read through this problem before continuing!
Solution 1
(Divide and Conquer)
Solution 2
(Set)
Line Segments
Focus Problem – read through this problem before continuing!
Solution
This section is not complete.
Problems
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| Old Gold | Normal | External Sol | ||||
| CEOI | Very Hard | Check CF | ||||
| Baltic OI | Very Hard | View Solution |
Manhattan MST
Focus Problem – read through this problem before continuing!
(KACTL code)
explanation? topcoder prob has
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!