Рамки
Вася и Петя играют в увлекательную игру. Правила просты: имеется две рамки, и игроки должны сдвинуть вторую рамку так, чтобы площадь пересечения рамок стала максимальной. Оба игрока обдумывают свои ходы в течение минуты и записывают вектор сдвига второй рамки. Побеждает тот, чей вектор обеспечивает большую площадь пересечения.
Игра полна нюансов, поэтому Вася решил схитрить и создать программу, которая найдет оптимальный вектор сдвига.
В этой игре рамка — это разность между двумя прямоугольниками: внутренним и внешним. Внутренний прямоугольник полностью находится внутри внешнего. Стороны обоих прямоугольников параллельны осям координат.
Чтобы сделать определение более понятным, рассмотрим несколько примеров.
Площадь рамки вычисляется как (W·H - w·h), где W, H — размеры внешнего прямоугольника, а w, h — размеры внутреннего (0 < w < W; 0 < h < H).
Напишите программу, которая определяет сдвиг одной рамки относительно другой, обеспечивающий максимальную площадь их пересечения.
Входные данные
Каждая рамка задается четырьмя точками — двумя противоположными углами внешнего прямоугольника, за которыми следуют два противоположных угла внутреннего прямоугольника. Точки задаются их координатами — парами целых чисел x и y. Координаты не превышают 10^8 по абсолютной величине.
Первая строка входного файла содержит описание первой рамки.
Вторая строка входного файла содержит описание второй рамки.
Выходные данные
Первая строка выходного файла должна содержать целое число A — максимально возможную площадь пересечения данных двух рамок, достижимую с помощью сдвига.
Вторая строка выходного файла должна содержать пару целых чисел x и y — координаты вектора сдвига второй рамки, который обеспечивает площадь пересечения A. Координаты не должны превышать 10^18 по абсолютной величине.