Имя входного файла: input.txt Имя входного файла:output.txt Ограничение по времени 2 секунды Ограничение по памяти 256Мбайт На плоскости заданы N различных точек. Нужно построить квадрат минимальной площади стороны которой параллельны осям X и Y, содержащий внутри и на границе все данные точки. Формат выходных данных. В первой строке записано единственное целое число N (2< N < 30). Далее в N строках задаются точки на плоскости (X,Y).Все координаты – целые и по абсолютной величине не превосход

Основная идея решения задачи заключается в поиске наименьшего прямоугольника, в котором будут содержатся все заданные точки.

Шаги решения задачи:

1. Прочитать входной файл и получить количество точек N и их координаты X, Y.
2. Найти минимальные и максимальные значения X и Y среди всех точек. Они будут соответствовать координатам вершин прямоугольника.
3. Рассчитать длину стороны прямоугольника как разность между максимальным и минимальным значением X.
4. Рассчитать ширину стороны прямоугольника как разность между максимальным и минимальным значением Y.
5. Найти максимальное значение между длиной и шириной стороны прямоугольника. Это будет длина стороны квадрата.
6. Записать полученное значение в выходной файл.

Обоснование решения:

По условию задачи, требуется построить квадрат минимальной площади, содержащий все заданные точки. Но так как стороны квадрата параллельны осям X и Y, то минимальный квадрат будет иметь сторону, равную максимальному значению между длиной и шириной прямоугольника, описанного вокруг точек. Таким образом, поиск минимального прямоугольника сводится к нахождению максимальной разницы между координатами X и Y, а затем использованию этого значения для определения стороны квадрата.

Сложность алгоритма:

Алгоритм выполняет простые математические операции и работает со всеми точками только один раз. Поэтому сложность алгоритма составляет O(N), где N – количество точек.