Rare
 0/14

Sweep Line

Authors: Benjamin Qi, Andi Qu

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.

Any help would be appreciated! Just submit a Pull Request on Github.

should the reader already be familiar with the 1D case (union of intervals on number line?) never explicitly mentioned in module

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.

Any help would be appreciated! Just submit a Pull Request on Github.

Problems

StatusSourceProblem NameDifficultyTags
Old GoldNormal
Show TagsSweep Line
COIHard
Show TagsSweep Line
CEOIHard
Show TagsSweep Line
CEOIVery Hard
Show TagsSweep Line
Baltic OIVery Hard
Show TagsSweep Line

Manhattan MST

Focus Problem – read through this problem before continuing!

(KACTL code)

explanation? topcoder prob has

StatusSourceProblem NameDifficultyTags
CSAHard
Show TagsManhattan MST

Radial Sweep

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

Focus Problem – read through this problem before continuing!

Solution - Seeing the Boundary

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

C++

#include <bits/stdc++.h>
#define x first
#define y second
typedef long long ll;
using namespace std;
const double PI = 4 * atan(1);
struct Event {
short type, id;

Problems

StatusSourceProblem NameDifficultyTags
CEOIEasy
Show TagsBinary Search, Radial Sweep
POINormal
Show TagsRadial Sweep
APIOHard
Show TagsRadial Sweep
JOIVery Hard
Show TagsRadial Sweep

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!