Sweep Line

The sign of a single 2D cross product tells you whether three points turn left, turn right, or are collinear, and that one signed scalar is the workhorse behind almost every algorithm in the plane. Convex hulls, polygon area, segment intersection, and point-in-polygon tests all reduce to a sequence of cross-product evaluations with a careful eye on edge cases. Get the geometric primitive right and the rest of the field follows. **Computational Geometry** introduces those primitives and the algorithms built on them. You will start with cross products and the orientation test, then implement convex-hull algorithms three ways: Graham scan in `O(n log n)` (sort by polar angle, maintain a stack with the orientation invariant), Jarvis march in `O(nh)` for hulls with few vertices, and Andrew's monotone chain. The lesson then covers line-segment intersection, the sweep-line algorithm for many segments, the closest-pair-of-points algorithm in 2D, polygon computations using the Shoelace formula, and the ray-casting point-in-polygon test. In **Sorting (Elementary)**, you learned the comparison-based sorting that drives polar-angle preprocessing. **Divide and Conquer (Advanced)** taught you the closest-pair `O(n log n)` template via the strip combine step, which reappears here. Next, **Advanced Tree Algorithms** moves from planar geometry back to hierarchical structures with Binary Lifting and centroid decomposition.

"For each element in the array, find the next greater element" is a brute-force `O(n^2)` problem until you notice that a stack maintained in decreasing order lets you answer every query as a side effect of a single left-to-right scan. The whole algorithm runs in `O(n)`, and the same monotonic-stack pattern solves trapping rain water, largest rectangle in a histogram, stock spans, and a long tail of related problems with the same template. **Advanced Greedy & Data Structures** is where greedy thinking meets specialized scaffolding. You will implement the monotonic stack pattern for next-greater and next-smaller variants, the monotonic deque for sliding-window maximum and minimum (also a key DP optimization), and sweep-line algorithms for interval and event problems (meeting rooms, interval merge, rectangle area union). The lesson closes with advanced greedy problems that need a heap or priority queue: full Huffman encoding, task scheduling with cooldown, the gas station problem, and activity selection with deadlines and profits. In **Greedy (Intro)**, you saw simple greedy strategies that needed only sorting. **Heaps & Priority Queue** taught you `O(log n)` access to the minimum or maximum, which is exactly what these advanced greedy patterns rely on for their efficiency. Next, **Branch and Bound** extends backtracking with the same kind of bounding-function pruning, applied to optimization search trees.