Rectangle Geometry

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

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)$ 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 {

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

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