PrevNext

You're not signed in!

Sign in to save your progress and sync your settings across devices.

Not Frequent
 0/5

Rectangle Geometry

Authors: Darren Yao, Michael Cao, Benjamin Qi, Allen Li, Andrew Wang

Problems involving rectangles whose sides are parallel to the coordinate axes.

Resources
IUSACOmodule is based off this

Most only include 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!

Think of this as the 1D analog of the next example.

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Example - Blocked Billboard

Focus Problem – read through this problem before continuing!

Naive Solution

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++

1#include <bits/stdc++.h>
2using namespace std;
3
4bool ok[2000][2000];
5
6int main() {
7 freopen("billboard.in","r",stdin);
8 freopen("billboard.out","w",stdout);
9 for (int i = 0; i < 3; ++i) {
10 int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

Java

1import java.io.*;
2import java.util.*;
3
4public class billboard
5{
6 public static void main(String[] args) throws IOException
7 {
8 BufferedReader br = new BufferedReader(new FileReader("billboard.in"));
9 PrintWriter out = new PrintWriter(new FileWriter("billboard.out"));
10 int ok[][] = new int[2000][2000];

Python

Unfortunately, the naive python solution will only get 9/10 test cases.

1import sys
2
3sys.stdin = open("billboard.in", "r")
4sys.stdout = open("billboard.out", "w")
5
6ok = [[False for i in range(2000)] for j in range(2000)]
7
8for i in range(3):
9 x1, y1, x2, y2 = map(int, input().split())
10 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.

Constant Time Solution

Official Analysis

A useful class in Java for dealing with rectangle geometry problems (though definitely overkill) is the built-in Rectangle class.

Java

To create a new rectangle, use the following constructor:

1// creates a rectangle with upper-left corner at (x,y) with a specified width and height
2Rectangle 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.
  • what happens when intersection is empty?

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

With Built-in Rectangle class:

1import java.awt.Rectangle; //needed to use Rectangle class
2import java.io.*;
3import java.util.*;
4
5public class blockedBillboard {
6 public static void main(String[] args) throws IOException{
7 Scanner sc = new Scanner(new File("billboard.in"));
8 PrintWriter pw = new PrintWriter(new FileWriter("billboard.out"));
9 int x1, y1, x2, y2;
10

Without Built-in Rectangle class:

1import java.io.*;
2import java.util.*;
3
4class Rect {
5 int x1, y1, x2, y2;
6 Rect() {}
7 int area() { return (y2-y1)*(x2-x1); }
8}
9
10public class blockedBillboard {
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++

Unfortunately, C++ doesn't have a built in rectangle struct or class, so you need to write the functions yourself. Here is the code from the official analysis (modified slightly):

1#include <bits/stdc++.h>
2using namespace std;
3
4struct Rect {
5 int x1,y1,x2,y2;
6 int area() { return (y2-y1)*(x2-x1); }
7};
8
9int intersect(Rect p, Rect q){
10 int xOverlap = max(0,min(p.x2,q.x2)-max(p.x1,q.x1));

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.

Python

Unfortunately, Python doesn't have a built in rectangle class, so you need to write the class yourself.

1import sys
2
3class Rect:
4 def __init__(self):
5 self.x1, self.y1, self.x2, self.y2 = map(int, input().split())
6
7 def area(self):
8 return (self.y2 - self.y1) * (self.x2 - self.x1)
9
10def intersect(p, q):

Problems

StatusSourceProblem NameDifficultyTagsSolution
BronzeVery Easy
Show Tags

rect

External Sol
BronzeEasy
Show Tags

rect

External Sol
CFNormal
Show Tags

rect

Check CF

Module Progress:

Give Us Feedback on Rectangle Geometry!

PrevNext