A Mindbending Scenario
Let's solve A Mindbending Scenario.
This problem is a little trickier than the other problems we've been through so far. It's always useful to spend a few minutes drawing a few possible inputs and solving them by hand. Drawing diagrams is useful for many reasons - it helps us to understand the problem, it helps us make sure we can read the input format correctly, and, if we are lucky, drawing diagrams may help us devise a solution.
Really, give it a go! I'll wait.
Initial thoughts
If the rectangles didn't overlap, then you could calculate the area of each rectangle separately, then add them together. If the rectangles do overlap, the overlapping part would get counted twice.
This gives us an interesting related question to consider: When do two rectangles overlap? Answering this question could form a piece of the solution, something like this:
If the rectangles do not overlap:
Sum the area of the rectangles individually.
else:
Sum the area of the rectangles individually.
Then subtract the area of the shared overlap....or it may not be part of our final solution — it's hard to tell at this stage. Even still, answering it may give us some insight into the problem.
Checking for overlap
It's easy enough for a human to look at two rectangles and say if they overlap or not (you did draw some of your inputs, right?), but the challenging part is being able to describe that in a way a computer would understand. Have a go yourself before reading on.
Here are some cases that I drew myself:
And here are a few ideas:
-
Two rectangles don't overlap if none of their sides intersect each other.
Putting aside how you would even check this condition (yuck!), this is unfortunately not correct. Two rectangles can overlap even if their sides don't touch. See if you can spot the case above. -
Two rectangles overlap if the corner of one rectangle is inside the other rectangle.
This one sounds pretty appealing, but two rectangles can intersect even if no corner of a rectangle is inside the other rectangle. See if you can spot the case above. -
Two rectangles overlap if there's a point that lies inside both rectangles.
This is similar to the previous one, but is actually correct! However, the tradeoff is that it isn't clear how we would check this more complex condition.
Let's think about that last one a bit more. How would we check if a point is inside a rectangle?
The exact condition is: For a rectangle with bottom-left corner \((x_1, y_1)\) and top-right corner \((x_2, y_2)\), a point \((x, y)\) is inside it if (and only if) \(x_1 \leq x \leq x_2\) and \(y_1 \leq y \leq y_2\).
Wait no, come back! I promise there isn't any complicated math going on here! Let's unpack that. Put in words, we're saying that a point is in a rectangle if:
- It is to the right of the left edge of the rectangle,
- It is to the left of the right edge of the rectangle,
- It is below the upper edge of the rectangle, and
- It is above the lower edge of the rectangle.
Think about it. If you're inside a (rectangular) room, then you're definitely to the right of its left wall. You can make similar statements about the other three walls.
If you're unfamiliar with cartesian coordinates and inequalities, you probably find the "in words" explanation easier to understand. But even so, you can appreciate how directly the mathematical explanation translates to code you can write. (That's not to say you can't solve this problem without thinking about it like this.)
Well okay, we know how to check if a point is inside one rectangle, what about if its inside two rectangles? Let's call the rectangles \(A\) and \(B\) to differentiate them. So \(A\)'s bottom-left corner is \((Ax_1, Ay_1)\) and its top-right corner is \((Ax_2, Ay_2)\). Similarly, \(B\)'s bottom-left corner is \((Bx_1, By_1)\) and its top-right corner is \((Bx_2, By_2)\). For a point to be in both rectangles, we need:
- \(Ax_1 \leq x \leq Ax_2\)
- \(Ay_1 \leq y \leq Ay_2\)
- \(Bx_1 \leq x \leq Bx_2\)
- \(By_1 \leq y \leq By_2\)
Let's focus on the conditions on \(x\).
We know that \(x\) needs to be at least \(Ax_1\) (since \(Ax_1 \leq x\)) and also at least \(Bx_1\) (since \(Bx_1 \leq x\)). But having both of these is redundant. If we create a new variable \(Ix_1\) which is equal to the larger of \(Ax_1\) and \(Bx_1\), we can succintly write: \(Ix_1 \leq x\) instead. "In words", we're saying that "you have to be to the right of the left edge of both rectangles. So whichever left edge is further to the right, that's the one we care about."
We know that \(x\) needs to be at most \(Ax_1\) (since \(x\leq Ax_2\)) and also at most \(Bx_2\) (since \(x \leq Bx_2\)). But having both of these is redundant. If we create a new variable \(Ix_2\) which is equal to the smaller of \(Ax_2\) and \(Bx_2\), we can succintly write: \(x \leq Ix_2 \) instead. "In words", we're saying that "you have to be to the left of the right edge of both rectangles. So whichever right edge is further to the left, that's the one we care about."
Combining both of those, we arrive at a final condition (for \(x\)): A point is inside both rectangles if (and only if) \(Ix_1 \leq x \leq Ix_2\). Similarly you can work out that the condition for \(y\) is \(Iy_1 \leq x \leq Iy_2\)
This looks a lot like the condition for a point being inside one rectangle. If you think about it, that makes sense: the overlapping area of two rectangles is also a rectangle. We have devised an algorithm for finding the rectangular overlap if it exists (which is different than what we set out to do initially, funny how things work out), all that's left to do is to see how our algorithm fails when there is no overlap at all. Can you adapt the algorithm to detect if no overlap exists?