Skip to content
CCC Python Course

Coordinate compression and sweep line

Stage
6
Module
M6.8
Lessons
1

In this module

  • Compress large coordinates into a dense rank map.
  • Build a 2D difference array on a compressed grid weighted by real dimensions.
  • Sweep over sorted events to compute coverage, not just a count.
  • Solve rectangle and interval problems that span large coordinate ranges.

Before this module

M4.3Prefix sums (1D, 2D, prefix/suffix max)M4.4Difference arrays and interval clampingM5.5Binary search

Lessons

  1. 1Coordinate compression and sweep line

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2014 S4
    Tinted Glass Window (opens on DMOJ in a new tab) DMOJ

    Find the total window area covered once several tinted panes overlap.