Rectangle Geometry

Why only rectangles

Contest geometry at this level is almost always axis-aligned rectangles. That restriction is a gift: every quantity you need is a sum, difference, or product of integer coordinates. No angles, no square roots, no floating point.

Keep it that way. The moment a solution involves double, you have introduced precision questions that the problem did not intend.

Representation

Store the two opposite corners. The convention that avoids the most bugs is lower-left and upper-right, with x1 < x2 and y1 < y2.

static class Rect {
    int x1, y1, x2, y2;      // (x1,y1) lower-left, (x2,y2) upper-right

    Rect(int x1, int y1, int x2, int y2) {
        this.x1 = Math.min(x1, x2);
        this.y1 = Math.min(y1, y2);
        this.x2 = Math.max(x1, x2);
        this.y2 = Math.max(y1, y2);
    }

    long area() {
        return (long)(x2 - x1) * (y2 - y1);
    }
}

Normalizing in the constructor is worth the three extra lines. Input does not always give corners in a predictable order, and every later computation assumes the ordering.

Note the cast in area(). With coordinates up to 10⁹, a width and height each around 2 × 10⁹ multiply to 4 × 10¹⁸, which overflows int badly. The (long) on the first operand promotes the whole expression.

Intersection

The overlap of two axis-aligned rectangles is itself an axis-aligned rectangle. Compute each dimension independently.

static long intersectionArea(Rect a, Rect b) {
    int w = Math.min(a.x2, b.x2) - Math.max(a.x1, b.x1);
    int h = Math.min(a.y2, b.y2) - Math.max(a.y1, b.y1);

    if (w <= 0 || h <= 0) return 0;      // no overlap
    return (long) w * h;
}

The overlap’s left edge is the rightmost of the two left edges; its right edge is the leftmost of the two right edges. If that produces a non-positive width, the rectangles do not overlap in x at all, and the intersection is empty.

int overlap = Math.max(0, Math.min(end1, end2) - Math.max(start1, start2));

Union of two rectangles

Add the areas and subtract the double-counted intersection.

long union = a.area() + b.area() - intersectionArea(a, b);

This is inclusion-exclusion. For three rectangles it becomes: add all three areas, subtract the three pairwise intersections, add back the triple intersection. The general form is in Inclusion-Exclusion.

For many rectangles the alternating sum has 2^N terms and stops being practical. That problem is solved by a coordinate sweep — see Sweep Line.

Perimeter and containment

long perimeter(Rect r) {
    return 2L * ((r.x2 - r.x1) + (r.y2 - r.y1));
}

// does a contain b entirely?
boolean contains(Rect a, Rect b) {
    return a.x1 <= b.x1 && a.y1 <= b.y1
        && a.x2 >= b.x2 && a.y2 >= b.y2;
}

// is a point inside, counting the boundary?
boolean containsPoint(Rect r, int px, int py) {
    return px >= r.x1 && px <= r.x2 && py >= r.y1 && py <= r.y2;
}

The 2L in perimeter promotes the arithmetic to long. Writing 2 * would compute in int first.

Distance without square roots

If you need to compare distances, compare squared distances. The comparison gives the same result and stays in integers.

static long distSquared(int x1, int y1, int x2, int y2) {
    long dx = x1 - x2;
    long dy = y1 - y2;
    return dx * dx + dy * dy;
}

Declaring dx and dy as long before multiplying is the important part. If they were int, dx * dx would be computed in int and could overflow before promotion.

Only take a square root when the problem asks for an actual distance as output, and then read the required tolerance from the statement.

Worked example

Given three axis-aligned rectangles, print the area covered by at least one.

long a1 = r[0].area(), a2 = r[1].area(), a3 = r[2].area();

long i12 = intersectionArea(r[0], r[1]);
long i13 = intersectionArea(r[0], r[2]);
long i23 = intersectionArea(r[1], r[2]);

// triple intersection: intersect the first two, then with the third
int x1 = Math.max(Math.max(r[0].x1, r[1].x1), r[2].x1);
int y1 = Math.max(Math.max(r[0].y1, r[1].y1), r[2].y1);
int x2 = Math.min(Math.min(r[0].x2, r[1].x2), r[2].x2);
int y2 = Math.min(Math.min(r[0].y2, r[1].y2), r[2].y2);
long i123 = (x2 > x1 && y2 > y1) ? (long)(x2 - x1) * (y2 - y1) : 0;

System.out.println(a1 + a2 + a3 - i12 - i13 - i23 + i123);

The triple intersection generalizes cleanly: the intersection of any number of axis-aligned rectangles is bounded by the maximum of the left edges and the minimum of the right edges.

Next