Square Pasture

Square Pasture
USACO easy

Farmer John has two rectangular pastures. He wants to replace them with one square pasture that covers both of them. The sides of the square must be parallel to the \(x\) and \(y\) axes.

Find the minimum area of such a square.

Input (file square.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 pasture.
  • Second line: four integers in the same format for the second pasture.

All coordinates are between \(0\) and \(10\), with \(x_2 > x_1\) and \(y_2 > y_1\). The pastures do not overlap or touch.

Output (file square.out):

  • One integer — the minimum area of the square.

Example:

Input:

6 6 8 8
1 8 4 9

Output:

49

(The square with corners \((1, 6)\) and \((8, 13)\) covers both pastures.)

Solution

First we find the smallest rectangle that covers both pastures. Its left side is the smaller of the two left sides, its right side is the larger of the two right sides, and the same holds for the bottom and top sides.

A square covers both pastures exactly when it covers this rectangle. So the side of the square must be at least the width and at least the height of the rectangle, and a square with side \(\max(\text{width}, \text{height})\) is enough. The answer is the square of this side.

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 main() {
    freopen("square.in", "r", stdin);
    freopen("square.out", "w", stdout);

    Rectangle a, b;
    cin >> a.bottom_left.x >> a.bottom_left.y >> a.top_right.x >> a.top_right.y;
    cin >> b.bottom_left.x >> b.bottom_left.y >> b.top_right.x >> b.top_right.y;

    // the smallest rectangle that contains both rectangles
    int left = min(a.bottom_left.x, b.bottom_left.x);
    int bottom = min(a.bottom_left.y, b.bottom_left.y);
    int right = max(a.top_right.x, b.top_right.x);
    int top = max(a.top_right.y, b.top_right.y);

    int side = max(right - left, top - bottom);
    cout << side * side << "\n";
}