📖 Chapter 2.5: Casework and Rectangle Geometry

⏱ Estimated reading time: 55 minutes | Difficulty: 🟢 Beginner (Core USACO Bronze Skill)

Prerequisites

• Basic C++ syntax (Chapters 2.1–2.2)
• if/else conditional statements
• Reading integers from input and printing output
• Understanding that x represents the horizontal coordinate and y represents the vertical coordinate in a Cartesian plane

🎯 Learning Goals

After finishing this chapter, you will be able to:

1. Recognize problems that require casework and systematically list all cases
2. Use the method “draw first, list boundaries next, then write code” to avoid missing cases
3. Handle rectangle intersection, coverage, and area problems on the coordinate plane
4. Determine whether two rectangles intersect and compute their intersection area
5. Use the difference array idea to count rectangle coverage on a grid
6. Understand and implement common USACO Bronze rectangle coverage problems

Learning Path for This Chapter

This chapter has two main themes:

1. Casework: When a problem has multiple possible situations, how do we handle them without missing or double-counting cases?
2. Rectangle geometry: When a problem involves coordinates, rectangles, coverage, or intersection, how do we convert the geometry into min/max and area calculations?

For beginners, the recommended learning order is:

Draw a picture to understand the problem
    ↓
Find key boundaries: equal, just touching, fully covering, fully separate
    ↓
Express those situations with if/else or min/max
    ↓
Test your code using samples and boundary cases you create yourself

💡 The focus of this chapter is not memorizing a single template, but learning how to break “complicated-looking situations” into clear, verifiable smaller cases.

2.5.1 Casework

What Is Casework?

When the answer to a problem depends on several “mutually exclusive situations,” we need to list these situations one by one and handle each separately.

Here are some simple examples:

• Is a number positive, negative, or zero?
• Are two intervals disjoint, just touching, or overlapping?
• Is a point inside a rectangle, on its boundary, or outside it?
• Is a rectangle partially covered by another rectangle?

These problems have one thing in common: you usually cannot finish with just one formula. You first need to determine which situation the current input belongs to.

Core principles:

1. Completeness: Do not miss any possible situation.
2. Mutual exclusiveness: Different situations should preferably not overlap; if they do overlap, make the priority clear.
3. Boundary checking: Pay special attention to cases such as equal, just touching, and just fully covering.

General Steps for Casework

When solving a casework problem, follow these four steps:

1. Draw a picture: Draw the objects in the problem, such as intervals, rectangles, or movement directions.
2. Find boundaries: Think about when the answer changes, such as when two interval endpoints become equal.
3. List cases: List all possible cases and try to make sure none are missing.
4. Write conditions: Translate each case into C++ if / else if / else statements.

For example:

if (first case) {
    // Handle the first case
} else if (second case) {
    // Handle the second case
} else {
    // Handle the remaining case
}

The final else is important. It often acts as a fallback: if none of the earlier explicitly listed cases are true, the program enters the final case.

Example: Classifying Two 1D Intervals

Problem statement:

Given two closed intervals [a, b] and [c, d], where a <= b and c <= d, determine their relationship:

1. Completely disjoint: There is a gap between the two intervals.
2. Touching at exactly one endpoint: The two intervals share one endpoint but do not overlap with positive length.
3. One contains the other: One interval completely covers the other interval.
4. Partially overlapping: The two intervals have a common part, but neither completely contains the other.

Before writing code, draw the cases first:

Case 1: Completely disjoint
[a-----b]   [c-----d]
or
[c-----d]   [a-----b]

Case 2: Touching at exactly one endpoint
[a-----b]
      [c-----d]     where b == c

Case 3: One interval contains the other
[a-----------b]
   [c-----d]

Case 4: Partially overlapping
[a--------b]
     [c--------d]

Now translate the picture into conditions.

Key Boundary: The Difference Between < and ==

• If b < c, then [a,b] is to the left of [c,d], with a gap between them.
• If b == c, then the two intervals only touch at one point.
• If b > c, then they overlap or one contains the other along the horizontal axis.

Therefore, when doing casework, we often handle more special cases first, such as “completely disjoint” and “touching at an endpoint.”

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

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;  // Intervals [a,b] and [c,d]

    // If the input does not guarantee left endpoint <= right endpoint, fix it first
    if (a > b) swap(a, b);
    if (c > d) swap(c, d);

    if (b < c || d < a) {
        cout << "Completely disjoint\n";
    } else if (b == c || d == a) {
        cout << "Touching at exactly one endpoint\n";
    } else if (a <= c && d <= b) {
        cout << "[c,d] is inside [a,b] (or equal)\n";
    } else if (c <= a && b <= d) {
        cout << "[a,b] is inside [c,d] (or equal)\n";
    } else {
        cout << "Partially overlapping\n";
    }
    return 0;
}

Beginner Question: Why Does the Order Matter?

In an if / else if chain, the program checks conditions from top to bottom. Once it finds the first true condition, it executes that block and skips the rest.

For example, the two intervals [1, 5] and [1, 5]:

• They satisfy [c,d] is inside [a,b].
• They also satisfy [a,b] is inside [c,d].

This is not necessarily wrong; it simply means the two intervals are equal. We only need to decide which output is appropriate for the classification required by the problem.

💡 If the problem asks you to handle “exactly equal” as a separate case, then write if (a == c && b == d) before the containment checks.

Casework Techniques

Technique 1: Sort or normalize input to reduce the number of cases

Sorting or normalizing input can merge symmetric cases:

// Example: ensure a <= b, so we do not need to separately handle a<b and a>b
if (a > b) swap(a, b);

Technique 2: Use min/max to simplify interval operations

If you only care about the overlap length of two intervals, you may not need to list all relationships. You can compute the intersection directly.

// Overlap length of intervals [a,b] and [c,d]
long long overlap = max(0LL, min(b, d) - max(a, c));

Meaning of this formula:

• The left endpoint of the intersection is the larger of the two left endpoints: max(a, c).
• The right endpoint of the intersection is the smaller of the two right endpoints: min(b, d).
• If the right endpoint is less than or equal to the left endpoint, there is no positive-length overlap.

Note: The formula above is suitable when treating intervals as [a,b) and [c,d), a “left-closed, right-open” length model. If you are working with closed intervals and counting integer points, the formula changes slightly.

Technique 3: Draw pictures and list boundary cases

For casework problems, draw the picture and verify all boundary cases one by one. At minimum, check:

• Completely separate
• Just touching
• Partially overlapping
• One completely containing the other
• Exactly equal

Technique 4: Prefer checking the easier opposite condition

Sometimes directly determining “intersecting” is complicated, but determining “not intersecting” is simple.

For example, two intervals are disjoint in only two ways:

b <= c || d <= a

So intersecting is the opposite:

!(b <= c || d <= a)

We will use the same idea for rectangle intersection.

USACO Bronze Typical: Direction Simulation

Problem statement (USACO style):

A cow stands on a 2D plane. Its initial position is (0, 0), and it initially faces north. Then N instructions are given. Each instruction is one of the following:

1. left: Turn left by 90 degrees in place.
2. right: Turn right by 90 degrees in place.
3. forward D: Move forward D steps in the current direction.

Output the cow’s final coordinates after all instructions are executed.

This looks like a simulation problem, but it also involves casework:

• Is the current direction north, east, south, or west?
• Is the current instruction a left turn, right turn, or forward movement?
• If moving forward, different directions change x and y differently.

Naive Approach: Direct Casework

The most intuitive implementation is:

if (dir == "N") y += d;
else if (dir == "S") y -= d;
else if (dir == "E") x += d;
else if (dir == "W") x -= d;

This is easy to understand, but if turning logic is also implemented with string-based casework, the code becomes long.

Cleaner Approach: Direction Indices

We can number the four directions clockwise:

0: North
1: East
2: South
3: West

Then turning right means adding 1, and turning left means subtracting 1. To avoid negative values, we can write:

// Turn left: dir - 1
// Add 4 to avoid a negative number, then take modulo 4
(dir + 3) % 4

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

int main() {
    // Direction encoding: 0=N, 1=E, 2=S, 3=W
    // dx/dy store the movement for each direction
    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};

    int x = 0, y = 0, dir = 0;  // Initial position and direction
    int n;
    cin >> n;

    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "left") {
            dir = (dir + 3) % 4;   // Turn left = (dir - 1 + 4) % 4
        } else if (cmd == "right") {
            dir = (dir + 1) % 4;   // Turn right
        } else {
            int d;
            cin >> d;
            x += dx[dir] * d;
            y += dy[dir] * d;
        }
    }

    cout << x << " " << y << "\n";
    return 0;
}

2.5.2 Rectangle Geometry

Representing Rectangles in a Coordinate System

In programming contests, rectangles are usually axis-aligned rectangles, meaning their sides are parallel to the coordinate axes. A rectangle is commonly represented by two opposite corners:

• Lower-left corner: (x1, y1)
• Upper-right corner: (x2, y2)

Usually:

x1 < x2, y1 < y2

Drawn on the coordinate plane:

y
↑
y2 +----------+
   |          |
y1 +----------+→ x
   x1        x2

If the problem does not guarantee x1 < x2 and y1 < y2, normalize after reading:

if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);

Why Is the Area (x2 - x1) * (y2 - y1)?

The width of the rectangle is the difference in x coordinates:

width = x2 - x1

The height of the rectangle is the difference in y coordinates:

height = y2 - y1

So the area is:

area = (x2 - x1) * (y2 - y1)

For example, for the rectangle from (1, 2) to (4, 6):

• Width: 4 - 1 = 3
• Height: 6 - 2 = 4
• Area: 3 * 4 = 12

Important Convention: Treat Rectangles as Half-Open Intervals

In many programming contest problems, a rectangle (x1, y1, x2, y2) represents:

x1 <= x < x2
y1 <= y < y2

That is, the left and bottom boundaries are included, while the right and top boundaries are excluded. This convention is useful because:

• The area is exactly (x2 - x1) * (y2 - y1).
• If two rectangles only touch at an edge, their intersection area is 0.
• It makes difference arrays for grid coverage easier to use.

For example, the rectangle (0,0)-(2,2) covers the following four 1×1 cells:

(0,1) (1,1)
(0,0) (1,0)

Its area is 2 * 2 = 4.

Determining Whether Two Rectangles Intersect

Key rule: Two rectangles do not intersect if and only if one rectangle is completely to the left, right, below, or above the other.

In other words, if any of the following is true, the two rectangles have no positive-area intersection:

1. A is to the left of B: ax2 <= bx1
2. B is to the left of A: bx2 <= ax1
3. A is below B: ay2 <= by1
4. B is below A: by2 <= ay1

One case in picture form:

A is to the left of B:

A             B
+---+         +---+
|   |         |   |
+---+         +---+
ax2 <= bx1

Therefore, to determine intersection, we can first check “not intersecting” and then take the opposite.

// Rectangle A: (ax1,ay1)-(ax2,ay2)
// Rectangle B: (bx1,by1)-(bx2,by2)
bool intersects(long long ax1, long long ay1, long long ax2, long long ay2,
                long long bx1, long long by1, long long bx2, long long by2) {
    // A is completely left/right/below/above B
    if (ax2 <= bx1 || bx2 <= ax1 || ay2 <= by1 || by2 <= ay1)
        return false;
    return true;
}

💡 We use <= here because if two rectangles only touch edge-to-edge, they do not have positive-area intersection.

Intersection Area

To compute the intersection of two rectangles, split the problem into two one-dimensional problems:

• Overlap length in the x direction
• Overlap length in the y direction

The lower-left and upper-right corners of the intersection rectangle are:

Intersection lower-left: max(two left boundaries), max(two bottom boundaries)
Intersection upper-right: min(two right boundaries), min(two top boundaries)

In code:

long long intersection_area(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 ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) return 0;  // No intersection, or only touching at boundary
    return (ix2 - ix1) * (iy2 - iy1);
}

Step-by-step example:

Rectangle A: (1,1)-(4,4)
Rectangle B: (2,2)-(6,5)

Step 1: Find the lower-left corner of the intersection
x = max(1,2) = 2
y = max(1,2) = 2
So the lower-left corner is (2,2)

Step 2: Find the upper-right corner of the intersection
x = min(4,6) = 4
y = min(4,5) = 4
So the upper-right corner is (4,4)

Step 3: Compute the area
width = 4 - 2 = 2
height = 4 - 2 = 2
area = 2 * 2 = 4

Now consider an example with no positive-area overlap:

Rectangle A: (0,0)-(2,2)
Rectangle B: (2,0)-(4,2)

They only touch at an edge.
Intersection width = min(2,4) - max(0,2) = 2 - 2 = 0
So the intersection area is 0.

Union Area of Two Rectangles

The union area of two rectangles means the area covered by at least one of them.

If we write:

Union area = area of A + area of B

there is a problem: the overlapping part is counted twice.

So we subtract the overlapping part once:

Union area = area of A + area of B - intersection area of A and B

This is the simplest form of the inclusion-exclusion principle.

long long union_area(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 areaA = (ax2 - ax1) * (ay2 - ay1);
    long long areaB = (bx2 - bx1) * (by2 - by1);
    long long inter = intersection_area(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
    return areaA + areaB - inter;
}

Example:

Area of rectangle A = 12
Area of rectangle B = 10
Overlapping area = 4

If directly added: 12 + 10 = 22, but the overlap was counted twice.
Correct answer: 12 + 10 - 4 = 18

💡 This formula is very useful for the union area of two rectangles. But for three or more rectangles, overlaps become more complicated, and we usually need sweep line, difference arrays, or a more systematic inclusion-exclusion method.

Point-in-Rectangle Test

When determining the relationship between a point and a rectangle, first check what the problem asks for:

• If the problem asks whether the point is inside the rectangle “including the boundary,” use <=.
• If the problem asks whether the point is strictly inside, use <.
• If the problem asks you to classify the boundary separately, check “boundary” and “inside” separately.

bool point_in_rect(long long px, long long py,
                   long long x1, long long y1, long long x2, long long y2) {
    return x1 <= px && px <= x2 && y1 <= py && py <= y2;
}

For example, for rectangle (0,0)-(3,2):

• Point (1,1) is inside.
• Point (0,1) is on the left boundary.
• Point (3,2) is on the upper-right corner.
• Point (4,1) is outside.

Advanced: Coverage Area of N Rectangles (Difference Array Method)

When many rectangles overlap, marking every grid cell for every rectangle may be too slow. If the coordinate range is small, we can use a 2D difference array to count how many times each cell is covered.

First Understand 1D Difference Arrays

Suppose we have an array and want to add 1 to every position in interval [l, r). We can write:

diff[l]++;
diff[r]--;

After computing prefix sums from left to right, we know how many times each position was added.

A 2D difference array uses the same idea, but it changes a “line segment” into a “rectangle.”

How Does a 2D Difference Array Add 1 to a Rectangle?

To add 1 to the covered area of rectangle [x1, x2) × [y1, y2), update four corners:

diff[y1][x1]++;
diff[y1][x2]--;
diff[y2][x1]--;
diff[y2][x2]++;

You can understand it as:

• Start adding the effect at the lower-left corner.
• Cancel the effect after the right boundary.
• Cancel the effect after the top boundary.
• The upper-right corner was canceled twice, so add it back once.

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

const int MAX_COORD = 1000;                 // Assume coordinates are in the range 0~1000
int diff[MAX_COORD + 2][MAX_COORD + 2];     // Allocate extra space for x2/y2 updates

// Add 1 to the rectangle [x1,x2) × [y1,y2)
void add_rect(int x1, int y1, int x2, int y2) {
    diff[y1][x1]++;
    diff[y1][x2]--;
    diff[y2][x1]--;
    diff[y2][x2]++;
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        add_rect(x1, y1, x2, y2);
    }

    // Restore the coverage count of each cell using 2D prefix sums
    for (int y = 0; y <= MAX_COORD; y++) {
        for (int x = 0; x <= MAX_COORD; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];
        }
    }

    // Count 1×1 cells covered by at least one rectangle
    // The largest lower-left corner is (999,999), because [999,1000) is the last cell
    long long covered = 0;
    for (int y = 0; y < MAX_COORD; y++) {
        for (int x = 0; x < MAX_COORD; x++) {
            if (diff[y][x] > 0) covered++;
        }
    }

    cout << covered << "\n";
    return 0;
}

Why Are We Counting Cells, Not Points?

When the coordinate range is 0~1000, the cells are usually:

Horizontal intervals: [0,1), [1,2), ..., [999,1000)
Vertical intervals:   [0,1), [1,2), ..., [999,1000)

So there are 1000 × 1000 cells of size 1×1. The array element diff[y][x] can be understood as the coverage count of the small cell whose lower-left corner is (x,y).

⚠️ Common Mistakes

Debugging Suggestions

After writing a rectangle solution, create these test cases yourself:

1. Completely disjoint: The answer should be 0.
2. Just touching at an edge: The intersection area should also be 0.
3. One rectangle completely contains the other: The intersection area should equal the smaller rectangle’s area.
4. Two rectangles are exactly the same: The intersection area should equal either rectangle’s area.
5. Only partially overlapping: Manually compute the width and height once, then compare with your program’s output.

Chapter Summary

The most important ideas in this chapter can be summarized in three sentences:

1. Draw before doing casework: Do not write conditions by intuition; draw all cases first.
2. Split rectangle problems into two directions: Handle the x direction and y direction separately, then combine the results.
3. Think of difference arrays for coverage problems: When there are many rectangles and the coordinate range is small, a 2D difference array is clearer than brute-force marking per rectangle.

Common formulas:

// Rectangle area
area = (x2 - x1) * (y2 - y1);

// Intersection boundaries of two rectangles
ix1 = max(ax1, bx1);
iy1 = max(ay1, by1);
ix2 = min(ax2, bx2);
iy2 = min(ay2, by2);

// Intersection area of two rectangles
intersection = max(0LL, ix2 - ix1) * max(0LL, iy2 - iy1);

💪 Exercises

🟢 Problem 1: Rectangle Intersection Area

Problem statement:

Given two axis-aligned rectangles A and B. Each rectangle is represented by four integers:

x1 y1 x2 y2

where (x1, y1) is the lower-left corner and (x2, y2) is the upper-right corner. It is guaranteed that x1 < x2 and y1 < y2.

Determine whether the two rectangles have a positive-area intersection:

• If they do, output the intersection area.
• If they do not, output 0.

Note: If two rectangles only touch at the boundary, such as when the right boundary of one rectangle equals the left boundary of another, the intersection area is 0.

Input format:

ax1 ay1 ax2 ay2
bx1 by1 bx2 by2

Output format:

One integer, the intersection area of the two rectangles

Sample input:

1 1 4 4
2 2 6 5

Sample output:

4

Sample explanation:

The intersection of the two rectangles is (2,2)-(4,4), with width 2, height 2, and area 4.

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

int main() {
    long long ax1, ay1, ax2, ay2;
    long long bx1, by1, bx2, by2;
    cin >> ax1 >> ay1 >> ax2 >> ay2;
    cin >> bx1 >> by1 >> bx2 >> by2;

    long long ix1 = max(ax1, bx1);
    long long iy1 = max(ay1, by1);
    long long ix2 = min(ax2, bx2);
    long long iy2 = min(ay2, by2);

    if (ix2 <= ix1 || iy2 <= iy1) {
        cout << 0 << "\n";
    } else {
        cout << (ix2 - ix1) * (iy2 - iy1) << "\n";
    }

    return 0;
}

🟡 Problem 2: Cow Grazing Area (USACO Bronze Style)

Problem statement:

Farmer John has N rectangular pastures. Each pasture is axis-aligned, and all coordinates are integers between 0 and 1000.

Each pasture is represented by its lower-left corner (x1, y1) and upper-right corner (x2, y2). It covers all 1×1 cells satisfying:

x1 <= x < x2
y1 <= y < y2

If multiple pastures overlap, the overlapping part is counted only once. Find the total number of cells covered by at least one pasture, which is also the total covered area.

Input format:

N
x1 y1 x2 y2
x1 y1 x2 y2
...

Output format:

One integer, the number of covered 1×1 cells

Sample input:

3
0 0 2 2
1 1 3 3
4 4 5 5

Sample output:

8

Sample explanation:

• The first pasture has area 4.
• The second pasture has area 4.
• They overlap by 1 cell.
• The third pasture has area 1.
• The total covered area is 4 + 4 - 1 + 1 = 8.

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

int diff[1002][1002];

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // Add 1 to the rectangle [x1,x2) × [y1,y2)
        diff[y1][x1]++;
        diff[y1][x2]--;
        diff[y2][x1]--;
        diff[y2][x2]++;
    }

    long long ans = 0;
    for (int y = 0; y <= 1000; y++) {
        for (int x = 0; x <= 1000; x++) {
            if (y > 0) diff[y][x] += diff[y - 1][x];
            if (x > 0) diff[y][x] += diff[y][x - 1];
            if (y > 0 && x > 0) diff[y][x] -= diff[y - 1][x - 1];

            // Only count 1×1 cells whose lower-left corner is (x,y), up to (999,999)
            if (x < 1000 && y < 1000 && diff[y][x] > 0) ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

🔴 Problem 3: Rectangle Classification Problem (Comprehensive)

Problem statement:

Given an axis-aligned rectangle and N points, determine the relationship between each point and the rectangle:

1. If the point is on one of the four sides of the rectangle, output Boundary.
2. If the point is inside the rectangle but not on the boundary, output Inside.
3. If the point is neither inside nor on the boundary, output Outside.

The rectangle is given by its lower-left corner (x1, y1) and upper-right corner (x2, y2). It is guaranteed that x1 < x2 and y1 < y2.

Input format:

x1 y1 x2 y2
N
px py
px py
...

Output format:

For each point, output one line: Boundary, Inside, or Outside.

Sample input:

0 0 4 3
5
1 1
0 2
4 3
5 1
2 3

Sample output:

Inside
Boundary
Boundary
Outside
Boundary

Sample explanation:

• (1,1) has both coordinates strictly inside the rectangle range, so it is inside.
• (0,2) is on the left boundary.
• (4,3) is the upper-right corner, so it is on the boundary.
• (5,1) is outside the rectangle.
• (2,3) is on the top boundary.

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

int main() {
    long long x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    int n;
    cin >> n;

    while (n--) {
        long long px, py;
        cin >> px >> py;

        bool on_vertical_edge = (px == x1 || px == x2) && (y1 <= py && py <= y2);
        bool on_horizontal_edge = (py == y1 || py == y2) && (x1 <= px && px <= x2);
        bool on_edge = on_vertical_edge || on_horizontal_edge;

        bool inside = x1 < px && px < x2 && y1 < py && py < y2;

        if (on_edge) cout << "Boundary\n";
        else if (inside) cout << "Inside\n";
        else cout << "Outside\n";
    }

    return 0;
}

🔴 Problem 4: USACO Bronze — Blocked Billboard

Problem statement:

Two billboards are placed on a wall. Later, a truck parks in front of the wall and blocks part of the visible area. The projections of the billboards and the truck on the wall can all be treated as axis-aligned rectangles.

You are given:

1. The rectangle coordinates of the first billboard.
2. The rectangle coordinates of the second billboard.
3. The rectangle coordinates of the truck’s blocking region.

Compute the total visible area of the two billboards.

Notes:

• The two billboards do not block each other.
• The truck may not block a billboard at all.
• The truck may block only part of a billboard.
• The truck may completely block a billboard.
• If the truck only touches the boundary of a billboard, the visible area does not decrease.

Input format:

Three lines, each containing 4 integers:

x1 y1 x2 y2
x1 y1 x2 y2
x1 y1 x2 y2

They represent billboard 1, billboard 2, and the truck’s blocking region respectively. Each rectangle is represented by its lower-left and upper-right corners.

Output format:

One integer, the total visible area of the two billboards

Sample input:

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

Sample output:

17

Sample explanation:

Billboard 1 has area (3 - 1) * (5 - 2) = 6. The intersection of the truck and billboard 1 is (2,2)-(3,3), with area 1, so the visible area of billboard 1 is 5.

Billboard 2 has area (10 - 6) * (4 - 0) = 16. The intersection of the truck and billboard 2 is (6,1)-(8,3), with area 4, so the visible area of billboard 2 is 12.

The total visible area is 5 + 12 = 17.

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

// Compute the intersection area of two rectangles
ll inter_area(ll ax1, ll ay1, ll ax2, ll ay2,
              ll bx1, ll by1, ll bx2, ll by2) {
    ll ix1 = max(ax1, bx1), iy1 = max(ay1, by1);
    ll ix2 = min(ax2, bx2), iy2 = min(ay2, by2);
    if (ix2 <= ix1 || iy2 <= iy1) return 0;
    return (ix2 - ix1) * (iy2 - iy1);
}

int main() {
    ll a1x1, a1y1, a1x2, a1y2;  // Billboard 1
    ll a2x1, a2y1, a2x2, a2y2;  // Billboard 2
    ll tx1, ty1, tx2, ty2;       // Truck
    cin >> a1x1 >> a1y1 >> a1x2 >> a1y2;
    cin >> a2x1 >> a2y1 >> a2x2 >> a2y2;
    cin >> tx1 >> ty1 >> tx2 >> ty2;

    ll area1 = (a1x2 - a1x1) * (a1y2 - a1y1);
    ll area2 = (a2x2 - a2x1) * (a2y2 - a2y1);
    ll covered1 = inter_area(a1x1, a1y1, a1x2, a1y2, tx1, ty1, tx2, ty2);
    ll covered2 = inter_area(a2x1, a2y1, a2x2, a2y2, tx1, ty1, tx2, ty2);

    cout << area1 + area2 - covered1 - covered2 << "\n";
    return 0;
}

💡 Chapter connection: Rectangle geometry is one of the high-frequency USACO Bronze topics (about 15%) and often combines with prefix sums or difference arrays. Once mastered, it can be directly applied to problems such as “coverage area” and “overlap detection.”