PrevNext
Not Frequent
 0/6

Rectangle Geometry

Authors: Darren Yao, Michael Cao, Benjamin Qi, Ben Dodge

Contributors: Allen Li, Andrew Wang, Dong Liu, Ryan Chou

Problems involving rectangles whose sides are parallel to the coordinate axes.

Edit This Page
Resources
IUSACO

module is based off this


Most problems in this category include only two or three squares or rectangles, in which case you can simply draw out cases on paper. This should logically lead to a solution.

Example - Fence Painting

Focus Problem – try your best to solve this problem before continuing!

Slow Solution

Time Complexity: O(max coordinate)\mathcal{O}(\text{max coordinate})

Solution

Fast Solution

Time Complexity: O(1)\mathcal{O}(1)

Solution

Example - Blocked Billboard

Think of this as the 2D analog of the previous example.

Focus Problem – try your best to solve this problem before continuing!

Slow Solution

Time Complexity: O((max coordinate)2)\mathcal{O}((\text{max coordinate})^2)

Solution

Fast Solution

Time Complexity: O(1)\mathcal{O}(1)

Solution

Common Formulas

Certain tasks show up often in rectangle geometry problems. For example, many problems involve finding the overlapping area of two or more rectangles based on their coordinate points, or determining whether two rectangles intersect. Here, we'll discuss these formulas.

Note that these formulas only apply to rectangles which have sides parallel to the coordinate axes.

Coordinates

A rectangle can be represented with 22 points: its top right corner and bottom left corner. We'll label these points trtr (top right) and blbl (bottom left).

In this module, we'll assume that increasing xx moves to the right and increasing yy moves up.

Finding area

The formula for finding the area of an individual rectangle is wlw \cdot l.

length\texttt{length} is the length of the vertical sides, and width\texttt{width} is the length of the horizontal sides.

  1. width=trxblx\texttt{width} = \texttt{tr}_x - \texttt{bl}_x
  2. length=trybly\texttt{length} = \texttt{tr}_y - \texttt{bl}_y
  3. area=widthlength\texttt{area} = \texttt{width} \cdot \texttt{length}

Implementation

C++

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

Java

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;
}

Python

def area(bl_x: int, bl_y: int, tr_x: int, tr_y: int) -> int:
length = tr_y - bl_y
width = tr_x - bl_x
return length * width

Checking if two rectangles intersect

Given two rectangles aa and bb, there are only two cases where they do not intersect:

  1. tray\texttt{tr}_{a_y} \leq blby\texttt{bl}_{b_y} or blay\texttt{bl}_{a_y} \geq trby\texttt{tr}_{b_y}.
  2. blax\texttt{bl}_{a_x} \geq trbx\texttt{tr}_{b_x} or trax\texttt{tr}_{a_x} \leq blbx\texttt{bl}_{b_x}.

In all other cases, the rectangles intersect.

Implementation

C++

bool intersect(vector<int> s1, vector<int> s2) {
int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
// no overlap
if (bl_a_x >= tr_b_x || tr_a_x <= bl_b_x
|| bl_a_y >= tr_b_y || tr_a_y <= bl_b_y) {
return false;
} else {
return true;
}
}

Java

boolean intersect(int[] s1, int[] s2) {
int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
// no overlap
if (bl_a_x >= tr_b_x || tr_a_x <= bl_b_x
|| bl_a_y >= tr_b_y || tr_a_y <= bl_b_y) {
return false;
} else {
return true;
}
}

Python

def intersect(s1, s2) -> bool:
bl_a_x, bl_a_y, tr_a_x, tr_a_y = s1[0], s1[1], s1[2], s1[3]
bl_b_x, bl_b_y, tr_b_x, tr_b_y = s2[0], s2[1], s2[2], s2[3]
# no overlap
if (bl_a_x >= tr_b_x or tr_a_x <= bl_b_x
or bl_a_y >= tr_b_y or tr_a_y <= bl_b_y):
return False
else:
return True

Finding area of intersection

We'll assume that the shape formed by the intersection of two rectangles is itself a rectangle.

First, we'll find this rectangle's length and width. width=min(trax,trbx)max(blax,blbx)\texttt{width} = \min(\texttt{tr}_{a_x}, \texttt{tr}_{b_x}) - \max(\texttt{bl}_{a_x}, \texttt{bl}_{b_x}). length=min(tray,trby)max(blay,blby)\texttt{length} = \min(\texttt{tr}_{a_y}, \texttt{tr}_{b_y}) - \max(\texttt{bl}_{a_y}, \texttt{bl}_{b_y}).

If either of these values are negative, the rectangles do not intersect. If they are zero, the rectangles intersect at a single point. Multiply the length and width to find the overlapping area.

Implementation

C++

int inter_area(vector<int> s1, vector<int> s2) {
int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
return (
(min(tr_a_x, tr_b_x) - max(bl_a_x, bl_b_x))
* (min(tr_a_y, tr_b_y) - max(bl_a_y, bl_b_y))
);
}

Python

def inter_area(s1, s2) -> int:
bl_a_x, bl_a_y, tr_a_x, tr_a_y = s1[0], s1[1], s1[2], s1[3]
bl_b_x, bl_b_y, tr_b_x, tr_b_y = s2[0], s2[1], s2[2], s2[3]
return (
(min(tr_a_x, tr_b_x) - max(bl_a_x, bl_b_x))
* (min(tr_a_y, tr_b_y) - max(bl_a_y, bl_b_y))
)

Java

int interArea(int[] s1, int[] s2) {
int bl_a_x = s1[0], bl_a_y = s1[1], tr_a_x = s1[2], tr_a_y = s1[3];
int bl_b_x = s2[0], bl_b_y = s2[1], tr_b_x = s2[2], tr_b_y = s2[3];
return (
(Math.min(tr_a_x, tr_b_x) - Math.max(bl_a_x, bl_b_x))
* (Math.min(tr_a_y, tr_b_y) - Math.max(bl_a_y, bl_b_y))
);
}

Problems

StatusSourceProblem NameDifficultyTags
BronzeVery Easy
Show TagsRectangle
BronzeEasy
Show TagsRectangle
CFNormal
Show TagsRectangle
CFNormal
Show TagsRectangle

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext