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.
Prerequisites
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
Since all the intervals lie between the range, , we can mark each interval of length contained within each interval as painted using a loop. Then the answer will be the number of marked intervals.
Time Complexity:
#include <bits/stdc++.h>using namespace std;const int MAX_POS = 100;int main() {freopen("paint.in", "r", stdin);freopen("paint.out", "w", stdout);int a, b, c, d;
However, this solution would not work for higher constraints (ex. if the coordinates were up to ).
Fast Solution
Calculate the answer by adding the original lengths and subtracting the intersection length.
The official analysis splits computing the intersection length into several cases. However, we can do it in a simpler way. An interval is contained within both and if , , , and , or in other words if, and . So the length of the intersection is if this quantity is positive and zero otherwise!
Time Complexity:
#include <bits/stdc++.h>using namespace std;int main() {freopen("paint.in", "r", stdin);freopen("paint.out", "w", stdout);int a, b, c, d;cin >> a >> b >> c >> d;
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:
Since all coordinates are in the range , we can simply go through each of the possible visible squares and check which ones are visible using nested for loops.
#include <bits/stdc++.h>using namespace std;const int MAX_POS = 2000;bool visible[MAX_POS][MAX_POS];int main() {freopen("billboard.in", "r", stdin);freopen("billboard.out", "w", stdout);for (int i = 0; i < 3; ++i) {
Of course, this wouldn't suffice if the coordinates were changed to be up to .
Fast Solution
Time Complexity:
Note how creating a struct Rect
to represent a rectangle makes the code easier
to understand.
#include <bits/stdc++.h>using namespace std;struct Rect {int x1, y1, x2, y2;int area() { return (y2 - y1) * (x2 - x1); }};int intersect(Rect p, Rect q) {int xOverlap = max(0, min(p.x2, q.x2) - max(p.x1, q.x1));
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 points: its top right corner and bottom left corner. We'll label these points (top right) and (bottom left).
In this module, we'll assume that increasing moves to the right and increasing moves up.
Finding area
The formula for finding the area of an individual rectangle is .
is the length of the vertical sides, and is the length of the horizontal sides.
Implementation
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;}
Checking if two rectangles intersect
Given two rectangles and , there are only two cases where they do not intersect:
- or .
- or .
In all other cases, the rectangles intersect.
Implementation
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 overlapif (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;}}
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. . .
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
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)));}
Problems
Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|
Bronze | Very Easy | Show TagsRectangle | |||
Bronze | Easy | Show TagsRectangle | |||
CF | Normal | Show TagsRectangle | |||
CF | 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!