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 | 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:
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. The code is provided here.
However, this solution would not work for higher constraints (ex. if the coordinates were up to ).
Fast Solution
Time Complexity:
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 do it more simply here. An interval is contained within both and if , , , and . In other words, and . So the length of the intersection is if this quantity is positive and zero otherwise!
C++
#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;
Python
import syssys.stdin = open("paint.in", "r")sys.stdout = open("paint.out", "w")a, b = map(int, input().split())c, d = map(int, input().split())total = (b-a) + (d-c)intersection = max(min(b, d)-max(a, c), 0)ans = total - intersectionprint(ans)
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:
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.
C++
#include <bits/stdc++.h>using namespace std;bool ok[2000][2000];int main() {freopen("billboard.in","r",stdin);freopen("billboard.out","w",stdout);for (int i = 0; i < 3; ++i) {int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
Java
import java.io.*;import java.util.*;public class billboard{public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new FileReader("billboard.in"));PrintWriter out = new PrintWriter(new FileWriter("billboard.out"));int ok[][] = new int[2000][2000];
Python
Unfortunately, the naive Python solution only passes 9/10 test cases.
import syssys.stdin = open("billboard.in", "r")sys.stdout = open("billboard.out", "w")ok = [[False for i in range(2000)] for j in range(2000)]for i in range(3):x1, y1, x2, y2 = map(int, input().split())x1 += 1000; y1 += 1000; x2 += 1000; y2 += 1000
Of course, this wouldn't suffice if the coordinates were changed to be up to .
Fast Solution
Time Complexity:
Java
Note how creating a class Rect
to represent a rectangle makes the code easier to understand.
import java.io.*;import java.util.*;class Rect {int x1, y1, x2, y2;Rect() {}int area() { return (y2-y1)*(x2-x1); }}public class blockedBillboard {
Alternative Implementation
We can also use the built-in Rectangle
class. To create a new rectangle, use the following constructor:
// creates a rectangle with upper-left corner at (x,y) with a specified width and heightRectangle newRect = new Rectangle(x, y, width, height);
The Rectangle
class supports numerous useful methods, including the following:
firstRect.intersects(secondRect)
checks if two rectangles intersect.firstRect.union(secondRect)
returns a rectangle representing the union of two rectangles.firstRect.contains(x, y)
checks whether the integer point exists in firstRect.firstRect.intersection(secondRect)
returns a rectangle representing the intersection of two rectangles.rect.isEmpty()
checks whetherrect
is empty.
This class can often lessen the implementation needed in some bronze problems and CodeForces problems.
Important Note About Java Coordinates
-coordinates in Java increase from top to bottom, not bottom to top! This is why we consider the top-left -coordinate of each rectangle in the solution below to be -y2
instead of y2
.
Alternatively, you can think of newRect
as creating a rectangle with lower-left corner at and work with Cartesian coordinates instead. So the solution below will work if all occurences of -y2
are replaced with y1
.
With Built-in Rectangle
class:
import java.awt.Rectangle; //needed to use Rectangle classimport java.io.*;import java.util.*;public class blockedBillboard {public static void main(String[] args) throws IOException{Scanner sc = new Scanner(new File("billboard.in"));PrintWriter pw = new PrintWriter(new FileWriter("billboard.out"));int x1, y1, x2, y2;
java.awt.geom.Area will allow you to calculate the union, intersection, difference, or exclusive or of arbitrary polygons (and more). See here for an example of usage.
C++
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));
Python
Note how creating a class Rect
to represent a rectangle makes the code easier to understand.
import sysclass Rect:def __init__(self):self.x1, self.y1, self.x2, self.y2 = map(int, input().split())def area(self):return (self.y2 - self.y1) * (self.x2 - self.x1)def intersect(p, q):
Problems
Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
---|---|---|---|---|---|---|
Bronze | Very Easy | Show Tagsrect | External Sol | |||
Bronze | Easy | Show Tagsrect | ||||
CF | Normal | Show Tagsrect | 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!
Give Us Feedback on Rectangle Geometry!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.