USACO 2017 December Contest Bronze Division - Blocked Billboard

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Simple rectangle intersection, a very important fact is that we don't have intersection between the first two rectangles.

Source codes

The source codes in C++ and Python can be seen below.

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

int main()
{
    ifstream cin("billboard.in");
    ofstream cout("billboard.out");

    int ans = 0;
    int xa, ya, xb, yb;
    cin >> xa >> ya >> xb >> yb;
    ans += (xb - xa) * (yb - ya);
    int xc, yc, xd, yd;
    cin >> xc >> yc >> xd >> yd;
    ans += (xd - xc) * (yd - yc);
    int xm, ym, xn, yn;
    cin >> xm >> ym >> xn >> yn;

    ans -= max(0, (min(xb, xn) - max(xa, xm))) * max(0, (min(yb, yn) - max(ya, ym)));
    ans -= max(0, (min(xd, xn) - max(xc, xm))) * max(0, (min(yd, yn) - max(yc, ym)));

    cout << ans;
    return 0;
}

with open("billboard.in", "r") as fin:
    tokens = fin.read().split()

billboard1 = [int(tokens[i]) for i in range(4)]
billboard2 = [int(tokens[i]) for i in range(4, 8)]
truck = [int(tokens[i]) for i in range(8, 12)]

area1 = (billboard1[2] - billboard1[0]) * (billboard1[3] - billboard1[1])
area2 = (billboard2[2] - billboard2[0]) * (billboard2[3] - billboard2[1])
ans = area1 + area2

def overlap_area(rect, cover):
    overlap_width = max(0, min(rect[2], cover[2]) - max(rect[0], cover[0]))
    overlap_height = max(0, min(rect[3], cover[3]) - max(rect[1], cover[1]))
    return overlap_width * overlap_height

ans -= overlap_area(billboard1, truck)
ans -= overlap_area(billboard2, truck)

with open("billboard.out", "w") as fout:
    fout.write(str(ans))