Задача №2913. Рамки
Вася с Петей играют в интересную игру. Правила ее очень простые: есть две рамки и участники должны передвинуть вторую рамку так, что площадь пересечения рамок была бы как можно большой. Оба игрока думают в течение минуты и записывают вектор переноса второй рамки. Побеждает тот игрок, чей вектор переноса дал большую площадь пересечения.
Игра имеет много частных случаев, так что Вася решил сжульничать и написать программу, находящую лучший вектор переноса.
В этой игре рамкой называется фигура, состоящая из двух прямоугольников: внешнего и внутреннего. Внутренний прямоугольник лежит строго внутри внешнего. Стороны обоих прямоугольников параллельны координатным осям.
На первом рисунке указаны (1) неправильные рамки, (2) правильные рамки, (3) пересечение рамок.
Площадь рамки вычисляется как W∙H – w∙h, где W, H – размеры внешнего прямоугольника, а w, h - размеры внутреннего (0 < w < W; 0 < h < H).
Напишите программу, которая находит перенос одной рамки относительно другой, которая даст максимальную площадь пересечения.
Каждая рамка описывается с помощью четырех точек — двух противоположных углов внешнего прямоугольника и двух противоположных углов внутреннего прямоугольника. Точки описываются своими координатами x и y, которые являются целыми числами и не превосходят 108 по модулю.
В первой строке содержится описание первой рамки, во второй — второй.
Первая строка выходного файла должна содержать целое число A – максимальная площадь области пересечения данных рамок достижимая с помощью переноса.
Вторая строка должна содержать пару целых чисел x и y – координаты вектора переноса второй рамки который даст область пересечения A. Координаты не должны превосходить 1018 по абсолютному значению.
2 2 5 6 3 3 4 5 0 0 10 10 2 2 3 3
10 0 -4