10556. Квадратное пастбище

 

Фермер Джон решил улучшить геометрию своей фермы. Раньше его коровы паслись на двух прямоугольных пастбищах. Фермер Джон хочет заменить их одним квадратным пастбищем минимального размера, который будет содержать эти два прямоугольника.

Помогите ФД вычислить минимальную площадь, которую станет занимать его новое пастбище (покрывающее два исходных прямоугольника).

 

Вход. Первая строка описывает одно из оригинальных прямоугольных пастбищ четырьмя целыми числами x1 y1 x2 y2 (все числа в диапазоне 0 ... 10). Левый нижний угол пастбища – точка (x1, y1), правый верхний угол – точка (x2, y2), причём x2 > x1 и y2 > y1.

Вторая строка аналогичным образом описывает второе прямоугольное пастбище. Оно не пересекается с первым и не касается его.

 

Выход. Выведите минимальную площадь квадратного пастбища, которое покроет оба прямоугольника.

 

Пример входа

Пример выхода

6 6 8 8

1 8 4 9

49

 

 

РЕШЕНИЕ

геометрия

 

Анализ алгоритма

Пусть прямоугольники задаются координатами:

·        (x1, y1) – (x2, y2): первый прямоугольник, x1 < x2, y1 < y2;

·        (x3, y3) – (x4, y4): второй прямоугольник, x3 < x4, y3 < y4;

 

Если (minx, miny) – (maxx, maxy) минимальный по площади прямоугольник, покрывающий эти два, то

·        minx = min(x1, x3), miny = min(y1, y3),

·        maxx = max(x2, x4), maxy = max(y2, y4),

 

Размеры покрывающего прямоугольника равны:

·        length = maxx – minx;

·        width = maxy – miny;

 

Размер стороны минимального по площади квадратного пастбища равен максимуму среди length и width.

 

Пример

Первый прямоугольник имеет углы (6, 6) и (8, 8). Второй прямоугольник имеет углы (1, 8) и (4, 9). Если нарисовать квадратный прямоугольник со стороной длины 7 и углами (1, 6) и (8, 13), то мы покроем исходные прямоугольники, и это наилучший вариант, поскольку невозможно покрыть исходные прямоугольники квадратом со стороной длины 6. Заметим, что существует несколько покрывающих квадратов со стороной длины 7, сдвинутых вертикально.

 

Реализация алгоритма

Инициализируем координаты прямоугольника, покрывающий два заданных.

 

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

 

Читаем данные входных прямоугольников. Вычисляем координаты покроывающего прямоугольника.

 

for (i = 0; i < 2; i++)

{

  cin >> a1 >> b1 >> a2 >> b2;

  if (a1 < minx) minx = a1;

  if (a2 > maxx) maxx = a2;

  if (b1 < miny) miny = b1;

  if (b2 > maxy) maxy = b2;

}

 

Вычисляем длину покрывающего квадрата

len = max(maxx – minx, maxy – miny)

 

len = maxx - minx;

if (maxy - miny > len) len = maxy - miny;

 

Выводим искомую площадь квадратного пастбища.

 

cout << len * len << endl;