Blocked Billboard

Blocked Billboard
USACO easy

Bessie looks at two rectangular billboards. A rectangular truck parks in front of them and may cover a part of them. Find the total area of both billboards that is still visible.

Input (file billboard.in):

  • First line: four integers \(x_1, y_1, x_2, y_2\) — the lower-left corner \((x_1, y_1)\) and the upper-right corner \((x_2, y_2)\) of the first billboard.
  • Second line: the second billboard in the same format.
  • Third line: the truck in the same format.

All coordinates are between \(-1000\) and \(1000\). The two billboards do not overlap (their common area is zero).

Output (file billboard.out):

  • One integer — the total visible area.

Example:

Input:

1 2 3 5
6 0 10 4
2 1 8 3

Output:

17

(\(5\) units of the first billboard and \(12\) units of the second billboard are visible.)

Solution

The billboards do not overlap, so we can handle each of them separately and add the results.

The visible part of a billboard is its area minus the area that the truck covers. The covered part is the intersection of the billboard and the truck, which we compute with the functions from the lesson:

  • if rectangles_intersect returns false, the whole billboard is visible;
  • otherwise we subtract the area of rectangle_intersection.

USACO reads the input from a file and writes the output to a file. freopen connects cin and cout to these files.

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

struct Point {
    int x;
    int y;
};

struct Rectangle {
    Point bottom_left;
    Point top_right;
};

int area(Rectangle r) {
    int width = r.top_right.x - r.bottom_left.x;
    int height = r.top_right.y - r.bottom_left.y;
    return width * height;
}

bool rectangles_intersect(Rectangle a, Rectangle b) {
    bool separated_x = a.top_right.x <= b.bottom_left.x ||
        b.top_right.x <= a.bottom_left.x;
    bool separated_y = a.top_right.y <= b.bottom_left.y ||
        b.top_right.y <= a.bottom_left.y;
    return !separated_x && !separated_y;
}

Rectangle rectangle_intersection(Rectangle a, Rectangle b) {
    Rectangle c;
    c.bottom_left.x = max(a.bottom_left.x, b.bottom_left.x);
    c.bottom_left.y = max(a.bottom_left.y, b.bottom_left.y);
    c.top_right.x = min(a.top_right.x, b.top_right.x);
    c.top_right.y = min(a.top_right.y, b.top_right.y);
    return c;
}

// area of the part of billboard b that the truck does not cover
int visible_area(Rectangle b, Rectangle truck) {
    if (!rectangles_intersect(b, truck)) {
        return area(b);
    }
    return area(b) - area(rectangle_intersection(b, truck));
}

Rectangle read_rectangle() {
    Rectangle r;
    cin >> r.bottom_left.x >> r.bottom_left.y >> r.top_right.x >> r.top_right.y;
    return r;
}

int main() {
    freopen("billboard.in", "r", stdin);
    freopen("billboard.out", "w", stdout);

    Rectangle b1 = read_rectangle();
    Rectangle b2 = read_rectangle();
    Rectangle truck = read_rectangle();

    cout << visible_area(b1, truck) + visible_area(b2, truck) << "\n";
}