PrevNext
Not Frequent
 0/5

Rectangle Geometry

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

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

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 – 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.

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 NameDifficultyTags
BronzeVery Easy
Show TagsRectangle
BronzeEasy
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