USACO Bronze 2018 January - Blocked Billboard II

Official Analysis

Solution 1

As described in the aforementioned editorial.

#include <iostream>
#include <cstdio>
using namespace std;

bool covered(int x, int y, int x1, int y1, int x2, int y2) {
	// returns true if (x, y) is covered by the rectangle bounded by (x1, y1) and (x2, y2)
	// returns false otherwise
	return x >= x1 && x <= x2 && y >= y1 && y <= y2;
}

fIn, fOut = open("billboard.in"), open("billboard.out", "w")

x1, y1, x2, y2 = map(lambda x: int(x), fIn.readline().split())
x3, y3, x4, y4 = map(lambda x: int(x), fIn.readline().split())

tlCorner = False
trCorner = False
brCorner = False
blCorner = False

Solution 2

As the problem statement says, the remaining cow feed billboard is situated in front of the lawnmower billboard, potentially obscuring it; therefore, we can split it into six cases to consider.

I will use the images to visualize the cases, so note these things: The red color shows the area covered by the second rectangle (whose borders are black), while the green one represents the area of the first rectangle (whose edges are blue). If two rectangles intersect, the red color will appear as the cow feed billboard block the lawnmower billboard.

We have to calculate the area of the first rectangle not obscured by the second one. There are 6 cases to consider, illustrated by the images below:

Case 1

In this case, both rectangles have the same coordinates, or the first rectangle lies in the area of the second one, so the answer is 0.

Case 2

Case 3

Case 4

Case 5

Case 6

The sixth case also includes a corner case where two rectangles intersect with their corners. In this case, if the intersection of two rectangles is at the corners (the top/down-left/right corners of the rectangles), we have to calculate the entire area of the first rectangle (the blue-edged rectangle). The image below illustrates the case:

#include <iostream>
#include <cstdio>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen("billboard.in","r",stdin);
	freopen("billboard.out","w",stdout);
	int x[5],y[5];
	for (int i=1;i<=4;++i) {