← jason

usaco bronze — blocked billboard

2017 december bronze, problem 1. rectangles, overlap, nothing fancier than that.

the setup

two billboards (guaranteed not to overlap each other) and a truck, all axis-aligned rectangles given by corner coordinates. the truck might be parked in front of one billboard, both, or neither. find the combined visible area of the two billboards once you subtract out whatever the truck is covering.

the approach

the only real idea here: overlap area between two axis-aligned rectangles is itself just a rectangle (or nothing), and you can get its width and height with a min/max trick — min(right edges) - max(left edges) for width, same idea for height. if either comes out non-positive, they don't overlap at all, overlap area is 0.

since the two billboards don't overlap each other, the truck's effect on each one is independent: compute each billboard's area, subtract its overlap with the truck, add the two results together. no need to think about double-counting anything.

sample

billboard 1 is 2×3 = 6, truck covers a 1×1 corner of it → 5 left. billboard 2 is 4×4 = 16, truck covers a 2×2 chunk → 12 left. 5 + 12 = 17.

solution

billboard.cpp

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

// overlap area between two axis-aligned rectangles, 0 if they don't touch
long long overlapArea(long long ax1, long long ay1, long long ax2, long long ay2,
                       long long bx1, long long by1, long long bx2, long long by2) {
    long long width  = min(ax2, bx2) - max(ax1, bx1);
    long long height = min(ay2, by2) - max(ay1, by1);
    if (width <= 0 || height <= 0) return 0;
    return width * height;
}

int main() {
    ifstream fin("billboard.in");
    ofstream fout("billboard.out");

    long long x1, y1, x2, y2, x3, y3, x4, y4, tx1, ty1, tx2, ty2;
    fin >> x1 >> y1 >> x2 >> y2;
    fin >> x3 >> y3 >> x4 >> y4;
    fin >> tx1 >> ty1 >> tx2 >> ty2;

    long long area1 = (x2 - x1) * (y2 - y1) - overlapArea(x1, y1, x2, y2, tx1, ty1, tx2, ty2);
    long long area2 = (x4 - x3) * (y4 - y3) - overlapArea(x3, y3, x4, y4, tx1, ty1, tx2, ty2);

    fout << (area1 + area2) << "\n";
    return 0;
}

compiled and checked against the sample above before this went on the page — output's 17, matches.