# 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:** $\mathcal{O}(\text{max coordinate})$

Since all the intervals lie between the range, $[0, 100]$, we can mark each interval of length $1$ 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 $10^9$).

### Fast Solution

**Time Complexity:** $\mathcal{O}(1)$

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 $[x,x+1]$ is contained within both $[a,b]$ and $[c,d]$ if $a\le x$, $c\le x$, $x<b$, and $x<d$. In other words, $\max(a,c)\le x$ and $x<\min(b,d)$. So the length of the intersection is $\min(b,d)-\max(a,c)$ 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:** $\mathcal{O}((\text{max coordinate})^2)$

Since all coordinates are in the range $[-1000,1000]$, we can simply go through each of the $2000^2$ 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 $10^9$.

### Fast Solution

**Time Complexity:** $\mathcal{O}(1)$

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 $(x,y)$ exists in firstRect.`firstRect.intersection(secondRect)`

returns a rectangle representing the intersection of two rectangles.`rect.isEmpty()`

checks whether`rect`

is empty.

This class can often lessen the implementation needed in some bronze problems and CodeForces problems.

### Important Note About Java Coordinates

$y$-coordinates in Java increase from top to bottom, not bottom to top! This is why we consider the top-left $y$-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 $(x,y)$ 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.