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 NameDifficultyTags
Bronze
Square Pasture
Very Easy
Show TagsRectangle
Bronze
Blocked Billboard II
Easy
Show TagsRectangle
CF
D3C - White Sheet
Normal
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!

Join Forum
PrevNext