Square Pasture#10556

Square Pasture (Editorial)

Suppose the coordinates of the rectangles are given as follows:

$(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2): the first rectangle, where $x_{1} < x_{2}$ x_1 < x_2 and $y_{1} < y_{2}$ y_1 < y_2,
$(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4): the second rectangle, where $x_{3} < x_{4}$ x_3 < x_4 and $y_{3} < y_{4}$ y_3 < y_4

Consider the smallest rectangle that completely covers both original rectangles. Let its opposite corners be $(min x, min y)$ (minx, miny) and $(ma xx, ma x y)$ (maxx, maxy). Then:

$min x = min (x_{1}, x_{3}), min y = min (y_{1}, y_{3})$ minx = min(x_1, x_3), miny = min(y_1, y_3),
$ma xx = ma x (x_{2}, x_{4}), ma x y = ma x (y_{2}, y_{4})$ maxx = max(x_2, x_4), maxy = max(y_2, y_4)

The dimensions of the covering rectangle are:

$l e n g t h = ma xx - min x$ length = maxx - minx,
$w i d t h = ma x y - min y$ width = maxy - miny

To completely cover both rectangles with a square, the side length of the square must be at least as large as both $l e n g t h$ length and $w i d t h$ . Therefore, the side length of the minimum square pasture is the maximum of these two values:

s i d e = ma x (l e n g t h, w i d t h)

side = max(length, width)

Example

Consider two original rectangles:

the first rectangle has its lower-left corner at $(6, 6)$ and its upper-right corner at $(8, 8)$ ,
the second rectangle has its lower-left corner at $(1, 8)$ and its upper-right corner at $(4, 9)$

Let's calculate the boundaries of the resulting rectangle:

$min x = min (6, 1) = 1, min y = min (6, 8) = 6$ minx = min(6, 1) = 1, miny = min(6, 8) = 6,
$ma xx = ma x (8, 4) = 8, ma x y = ma x (8, 9) = 9$ maxx = max(8, 4) = 8, maxy = max(8, 9) = 9

The dimensions of the covering rectangle are:

$l e n g t h = 8 - 1 = 7$ length = 8 - 1 = 7,
$w i d t h = 9 - 6 = 3$ width = 9 - 6 = 3

The side length of the covering square is:

s i d e = ma x (7, 3) = 7

side = max(7, 3) = 7

Therefore, the area of the minimum covering square is $7^{2} = 49$ 7^2 = 49.

Algorithm implementation

Initialize the boundaries of the covering rectangle. Since the coordinates are in the range from $0$ to $10$ , we can set the initial values as follows:

minx = 10; maxx = 0; miny = 10; maxy = 0;

Read the coordinates of the two original rectangles. For each rectangle, update the boundaries of the covering rectangle.

for (i = 0; i < 2; i++)
{
  scanf("%d %d %d %d", &a1, &b1, &a2, &b2);
  if (a1 < minx) minx = a1;
  if (a2 > maxx) maxx = a2;
  if (b1 < miny) miny = b1;
  if (b2 > maxy) maxy = b2;
}

C++

Calculate the length and width of the covering rectangle.

l = maxx - minx;
w = maxy - miny;

To cover this rectangle with a square, the side length of the square must be at least as large as both its length and its width. Therefore, we choose the larger of the two values.

len = (l > w) ? l : w;

Calculate the area of the square and print the answer.

area = len * len;
printf("%d\n", area);