PrevNext
Not Frequent
 0/5

Rectangle Geometry

Authors: Darren Yao, Michael Cao, Benjamin Qi, Allen Li, Andrew Wang, Dong Liu

Prerequisites

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

Resources
IUSACO
7.1 - Rectangle Geometry
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

Fence Painting

Bronze - Very Easy

Focus Problem – read through 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.

Blocked Billboard

Bronze - Easy

Focus Problem – read through 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

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
Bronze
Square Pasture
Very Easy
Show Tags

Rectangle

Internal Sol
Bronze
Blocked Billboard II
Easy
Show Tags

Rectangle

Internal Sol
CF
D3C - White Sheet
Normal
Show Tags

Rectangle

Check CF

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!

Join Forum
PrevNext