Tap here to switch tabs
Problem
Submissions

Problem: Rectangle Area II

Rectangle Area II gives you axis-aligned rectangles and asks for the total area covered by their union, counting overlaps once and returning the result modulo a large prime.

Statement

You are given a 2D2 {D} array rectangles where rectangles[i] = [xi1,yi1,xi2,yi2][x_{i1}, y_{i1}, x_{i2}, y_{i2}] represents the ithi^{ {th}} rectangle with bottom left coordinates (xi1,yi1)(x_{i1}, y_{i1}) and top right coordinates (xi2,yi2)(x_{i2}, y_{i2}).

Calculate the total area covered by all given rectangles in the plane. Any area covered by overlapping rectangles must only be counted once.

Return the total area modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq rectangles.length ≤200\leq 200

  • rectangles[i].length =4= 4

  • 0≤xi1,yi1,xi2,yi2≤1090 \leq x_{i1}, y_{i1}, x_{i2}, y_{i2} \leq 10^9

  • xi1≤xi2x_{i1} \leq x_{i2}

  • yi1≤yi2y_{i1} \leq y_{i2}

  • All rectangles have non zero area.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Rectangle Area II

Rectangle Area II gives you axis-aligned rectangles and asks for the total area covered by their union, counting overlaps once and returning the result modulo a large prime.

Statement

You are given a 2D2 {D} array rectangles where rectangles[i] = [xi1,yi1,xi2,yi2][x_{i1}, y_{i1}, x_{i2}, y_{i2}] represents the ithi^{ {th}} rectangle with bottom left coordinates (xi1,yi1)(x_{i1}, y_{i1}) and top right coordinates (xi2,yi2)(x_{i2}, y_{i2}).

Calculate the total area covered by all given rectangles in the plane. Any area covered by overlapping rectangles must only be counted once.

Return the total area modulo 109+710^9 + 7.

Constraints:

  • 1≤1 \leq rectangles.length ≤200\leq 200

  • rectangles[i].length =4= 4

  • 0≤xi1,yi1,xi2,yi2≤1090 \leq x_{i1}, y_{i1}, x_{i2}, y_{i2} \leq 10^9

  • xi1≤xi2x_{i1} \leq x_{i2}

  • yi1≤yi2y_{i1} \leq y_{i2}

  • All rectangles have non zero area.