Sweep Line

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).

Closest Pair

Solution 1

(Divide and Conquer)

Solution 2

(Set)

Line Segments

Solution

Problems

Manhattan MST

(KACTL code)

explanation? topcoder prob has

Radial Sweep

Solution - Seeing the Boundary

#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