Frames#2263
Vasya and Petya are playing a game. The rules are simple: there are two frames, and the players must translate the second frame so that the area of intersection between the frames becomes as large as possible. Both players have a minute to think and write down the translation vector of the second frame. The player whose vector results in a larger intersection area wins.
The game involves many subtleties, so Vasya decided to write a program to find the optimal translation vector.
For this game, a frame is defined as the difference between two rectangles: the inner and the outer rectangle. The inner rectangle must be strictly inside the outer rectangle. The sides of both rectangles are parallel to the coordinate axes.
The area of the frame is calculated as W \cdot H - w \cdot h, where and are the dimensions of the outer rectangle, and and are the dimensions of the inner rectangle (0 < w < W;\ 0 < h < H).
Write a program that, given two frames, finds such a translation of the second frame (relative to the first) that the intersection area of the frames is maximized.
Each frame is specified by four points: two opposite corners of the outer rectangle, followed by two opposite corners of the inner rectangle. Each point is described by a pair of integer coordinates and . The absolute value of any coordinate does not exceed 10^8.
The first line of the input file contains the description of the first frame.
The second line of the input file contains the description of the second frame.
The first line of the output file must contain an integer — the maximal possible intersection area of the two given frames, achievable by translating the second frame.
The second line of the output file must contain a pair of integers and — the coordinates of the translation vector of the second frame that provide the intersection area . The absolute value of each coordinate must not exceed 10^{18}.
Example 1