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})

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

Fast Solution

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

Calculate the answer by adding the original lengths and subtracting the intersection length.

(b−a)+(d−c)−intersection([a,b],[c,d])(b-a)+(d-c)-\text{intersection}([a,b],[c,d])

The official analysis splits computing the intersection length into several cases. However, we do it more simply here. An interval [x,x+1][x,x+1] is contained within both [a,b][a,b] and [c,d][c,d] if a≤xa\le x, c≤xc\le x, x<bx<b, and x<dx<d. In other words, max⁡(a,c)≤x\max(a,c)\le x and x<min⁡(b,d)x<\min(b,d). So the length of the intersection is min⁡(b,d)−max⁡(a,c)\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 sys


sys.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 - intersection


print(ans)

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)

Since all coordinates are in the range [−1000,1000][-1000,1000], we can simply go through each of the 200022000^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 sys


sys.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 10910^9.

Fast Solution

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

Official Analysis

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 height
Rectangle 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)(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

yy-coordinates in Java increase from top to bottom, not bottom to top! This is why we consider the top-left yy-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)(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 class
import 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;
Optional

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.

What's a struct?

A C++ struct is the same as a C++ class but all members are public rather than private by default. Check LCPP for more information.

#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 sys


class 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

StatusSourceProblem NameDifficultyTagsSolutionURL
Bronze
Square Pasture
Very Easy
Show Tags

rect

External Sol
Bronze
Blocked Billboard II
Easy
Show Tags

rect

Internal Sol
CF
D3C - White Sheet
Normal
Show Tags

rect

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!

Join Forum

Give Us Feedback on Rectangle Geometry!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext