### You're not signed in!

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

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

IUSACO | module 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.

## Example - Blocked Billboard

Focus Problem â€“ read through this problem before continuing!

### Naive Solution

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

1#include <bits/stdc++.h>2using namespace std;34bool ok[2000][2000];56int 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.*;34public class billboard5{6 public static void main(String[] args) throws IOException7 {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 sys23sys.stdin = open("billboard.in", "r")4sys.stdout = open("billboard.out", "w")56ok = [[False for i in range(2000)] for j in range(2000)]78for 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 $10^9$.

### Constant Time Solution

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 height2Rectangle 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.- 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 class2import java.io.*;3import java.util.*;45public 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.*;34class Rect {5 int x1, y1, x2, y2;6 Rect() {}7 int area() { return (y2-y1)*(x2-x1); }8}910public class blockedBillboard {

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;34struct Rect {5 int x1,y1,x2,y2;6 int area() { return (y2-y1)*(x2-x1); }7};89int intersect(Rect p, Rect q){10 int xOverlap = max(0,min(p.x2,q.x2)-max(p.x1,q.x1));

Python

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

1import sys23class Rect:4 def __init__(self):5 self.x1, self.y1, self.x2, self.y2 = map(int, input().split())67 def area(self):8 return (self.y2 - self.y1) * (self.x2 - self.x1)910def intersect(p, q):

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

Bronze | Very Easy | ## Show Tagsrect | External Sol | ||

Bronze | Easy | ## Show Tagsrect | External Sol | ||

CF | Normal | ## Show Tagsrect | Check CF |