Хотите стать миллиардером? Это элементарно! Достаточно всего лишь автоматизировать какой-нибудь широко распространённый ручной труд, и на сэкономленные деньги можно будет смело покупать желанный красный Ferrari.
Вот, например, почему бы не автоматизировать процесс написания бульварных детективов? Или, скажем, процесс сочинения песен для наших поп-звёзд? Нет! Это все слишком просто и не достойно настоящего программиста! В этой задаче вам придётся автоматизировать нечто более возвышенное — процесс создания настоящих картин! Только подумайте: великолепные пейзажи, искусные натюрморты, величественные портреты и даже виртуозные автопортреты станут по силам простому домашнему компьютеру!
По правде сказать, сам алгоритм рисования уже реализовал ваш коллега программист Петров. Его алгоритм формирует описания мазков кистью; достаточно подать эти данные на вход плоттера и картина через пару
часиков будет готова!
А чтобы не терять зря драгоценные часы, в это время можно заниматься изготовлением рамки для будущей картины. Вот тут-то и попал впросак ваш коллега Петров. Не получается у него вычислить по списку мазков размер будущей картины…
Всё было бы элементарно, если бы мазки представляли из себя обычные отрезки прямой, но ведь все новаторство алгоритма Петрова и состояло в том, что мазки у него имели форму своеобразных уголочков. Чтобы получить такой мазок надо провести кистью (или плоттером) X миллиметров в одном направлении, потом повернуть на 90 градусов по часовой стрелке и провести ещё X миллиметров. Вот так выглядит новаторский мазок Петрова.
Исходные данные
Дано N (0 ≤ N ≤ 100000) строк с числами, по одной строке на мазок. Каждый мазок описывается четырьмя целыми числами: координаты начальной точки мазка и координаты конечной точки мазка. Все числа не превосходят 10000 по абсолютному значению.
Результат
На выходе должно быть всего 2 числа: ширина и высота минимальной рамки для будущей картины. Числа следует разделять пробелом и выводить их с точностью 4 знака после десятичной точки.
Заметьте, что вписывая картину в рамку, её нельзя поворачивать, даже если это и приведёт к уменьшению размеров рамки. Ведь ваша задача не сэкономить на материалах, а просто сделать для готовой картины подходящую рамку. Кроме того, все мазки должны содержаться в готовой картине целиком.
Пример
исходные данные | результат |
---|
0 0 1 1
1 1 2 0
2 0 0 0
2 0 3 0
| 3.0000 2.0000
|
Автор задачи: Павел Егоров
Источник задачи: IX Чемпионат Урала по программированию. Екатеринбург, УрГУ, 19-24 апреля 2005г.