Rectangular Geometry

Rectangular geometry deals with rectangles whose sides are aligned with the coordinate axes. In this section we focus on the basic ideas of these axis-parallel rectangles.

Note

We assume the positive \(X\)-axis points to the right and the positive \(Y\)-axis points upward.

Representing Rectangles

Rectangles can be represented by two coordinate points, either the top-left and bottom-right corners or the top-right and bottom-left corners.

Note

In this section we’ll represent a rectangle using its top-right and bottom-left coordinates, where \(tr_x\) and \(tr_y\) are the coordinates of the top-right point, and \(bl_x\) and \(bl_y\) are the coordinates of the bottom-left point.

Common Formulas

Length and Width

\(length\) is the vertical side of the rectangle while \(width\) is the horizontal side.

\(width = tr_x - bl_x\)

\(length = tr_y - bl_y\)

Area

The \(area\) of a rectangle is the product of \(length\) and \(width\).

\(area = length \cdot width\)

int area(int bl_x, int bl_y, int tr_x, int tr_y) {
  int length = tr_y - bl_y;
  int width = tr_x - bl_x;
  return length * width;
}

Check Intersection

To determine whether two rectangles \(a\) and \(b\) intersect, both their \(X\)-ranges and \(Y\)-ranges must overlap. It is often easier to check the opposite: determine whether at least one dimension doesn’t intersect. If either the \(X\) dimension or the \(Y\) dimension does not overlap, then the rectangles do not intersect.

For \(Y\) dimension:

\(a_{tr_y} \le b_{bl_y}\) or \(b_{tr_y} \le a_{bl_y}\)

For \(X\) dimension:

\(a_{tr_x} \le b_{bl_x}\) or \(b_{tr_x} \le a_{bl_x}\)

If any of those apply, the rectangles doesn’t intersect. otherwise they will intersect.

bool are_intersected(int a_tr_x , int a_tr_y, int a_bl_x, int a_bl_y, int b_tr_x , int b_tr_y, int b_bl_x, int b_bl_y) {
  if(a_tr_y <= b_bl_y || b_tr_y <= a_bl_y || a_tr_x <= b_bl_x || b_tr_x <= a_bl_x) {
    return false;
  }
  else {
    return true;
  }
}

Finding Intersection

If two rectangles \(a\) and \(b\) intersect then the rectangel \(c\) that is the intersection of \(a\) and \(b\) will be:

\(c_{tr_x} = min(a_{tr_x}, b_{tr_x})\)

\(c_{tr_y} = min(a_{tr_y}, b_{tr_y})\)

\(c_{bl_x} = max(a_{bl_x}, b_{bl_x})\)

\(c_{bl_y} = max(a_{bl_y}, b_{bl_y})\)

Single Dimensional Formulas

This geometry also applies in one-dimensional space, where we work with intervals instead of rectangles. An interval is represented by two numbers, \(l\) and \(r\), which denote the beginning and end of the interval.

Formulas

Length

\(length\) is the area covered by the interval.

\(length = r - l\)

Check Intersection

For two intervals \(a\) and \(b\) in one dimension, we can check whether they do not intersect. If one interval lies entirely to the left or right of the other, they do not overlap. Otherwise, the intervals intersect:

\(a_{r} \le b_{l}\) or \(b_{r} \le a_{l}\)

bool are_intersected(int a_l , int a_r, int b_l , int b_r) {
  if(b_r <= a_l || a_r <= b_l) {
    return false;
  }
  else {
    return true;
  }
}

Finding Intersection

If two intervals \(a\) and \(b\) intersect then the interval \(c\) that is the intersection of \(a\) and \(b\) will be:

\(c_{l} = max(a_{l}, b_{l})\)

\(c_{r} = min(a_{r}, b_{r})\)

Example Task

Fence Painting

USACO

we are given two intervals and are asked to print the total length covered by these intervals.

Solution

If the two give intervals don’t intersect then the area cover is the sum of both lengths. Otherwise, the solution will be the sum of both lengths subtracted by the intersected area.

#include <iostream>

using namespace std;

int main() {
  // these two lines are just to do i/o in USACO
  freopen("paint.in", "r", stdin);
    freopen("paint.out", "w", stdout);

    int a_l , a_r, b_l , b_r;
  
  cin >> a_l >> a_r >> b_l >> b_r;

  // c represents the intersection between a and b.
  int c_l = max(a_l, b_l), c_r = min(a_r, b_r);

  int total = (a_r - a_l) + (b_r - b_l);
  int intersection = (c_r - c_l);
  
  // now we need to check if a and b don't intersect
  if(b_l > a_r || a_l > b_r){
    cout << total << "\n";
  }
  else{
    cout << total - intersection << "\n";
  }
}