Video Solution

By Varun Ragunath

Official Analysis (C++)

Explanation

There are many ways to solve the problem, but the easiest way is to imagine cutting the white sheet.

Everytime the white sheet is covered by a black sheet, we can imagine cutting the intersection between the black and white sheets. Then, if the area of the final white sheet after being cut by the two rectangles is greater than zero, there is a portion of the white sheet that is visible.

However, when considering cutting the sheet, the portion that is being cut must cut from entirely $x_{1}$->$x_{2}$ or $y_{1}$->$y_{2}$ or else there will be a portion of the white sheet still shown. We only cut when a black sheet completely covers the entire width or length of the white sheet, otherwise there will still be bits and pieces shown.

There are 4 instances of which a white sheet can cover a black sheet.

$\textbf{Top: }$ From the top, if the white sheet is completely covered from $x_{1}$->$x_{2}$ or $y_{1}$->$y_{2}$ and intersects some part of a black sheet, then change the $y_{2}$ (top of the rectangle) to the bottom of the black rectangle.

$\textbf{Bottom: }$ From the bottom, if the white sheet is completely covered from $x_{1}$->$x_{2}$ and intersects some part of a black sheet, then change the $y_{1}$ (bottom of the rectangle) to the top of the black rectangle.

$\textbf{Left: }$ From the left, if the white sheet is completely covered from $y_1$ to $y_2$ and intersects some part of a black sheet, then change the $x_1$ (left edge of the rectangle) to the right edge of the black rectangle.

$\textbf{Right: }$ From the right, if the white sheet is completely covered from $y_1$ to $y_2$ and intersects some part of a black sheet, then change the $x_2$ (right edge of the rectangle) to the left edge of the black rectangle.

Also, keep in mind to make sure that $x_1$ is always $<$ $x_2$ and the same with $y_1$ and $y_2.$

Since there are no for loops or any sort of repetitions, the time complexity is $\mathcal{O}(1)$

Implementation

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

Copy
#include <bits/stdc++.h>
using namespace std;

struct Rect {
	int x1, y1, x2, y2;
	int area() { return (x2 - x1) * (y2 - y1); }
};

/*
   Main Idea: If B intersects entirely in the x or y direction, cut it.

Copy
class Rect:
	def __init__(self, a: int, b: int, c: int, d: int):
		self.x1, self.y1, self.x2, self.y2 = a, b, c, d


"""
Main Idea: If B intersects entirely in the x or y direction, cut it.
This method cuts rectangle A based on rectangle B. (A - white sheet, B - black sheet)
We can cut rectangle A if B covers all of x1->x2 or y1->y2.
"""

Copy
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();
		Rect A = new Rect(io.nextInt(), io.nextInt(), io.nextInt(), io.nextInt());
		Rect B = new Rect(io.nextInt(), io.nextInt(), io.nextInt(), io.nextInt());
		Rect C = new Rect(io.nextInt(), io.nextInt(), io.nextInt(), io.nextInt());