Задача H для тренировки в сентябре
Первоисточник: ACM ICPC 2010 - 2011, NEERC, Northern Subregional Contest, St Petersburg, October 30, 2010
Задачу добавил: elena
Успешно сдано решений: 3
Problem F. FramesTime limit: 3 seconds
Memory limit: 256 megabytes
Vasya and Petya are playing an interesting game. Rules are pretty easy: there are two frames, the players have to make a translation of the second frame in such a way that the area of the intersection of the frames would be as large as possible. Both players think for a minute, and write down the translation vector of the second frame. The player whose vector gives a larger intersection area wins.
The game has many subtle cases, so Vasya wants to cheat and write a program that finds the best translation vector.
For this game the frame is a difference of two rectangles: the inner one and the outer one. The inner rectangle lies strictly inside the outer one. Sides of both rectangles are parallel to the coordinate axes.
To make the definition more clear let us consider some examples.
Incorrect frames
Correct Frames
Frames intersection
The area of the frame is (W · H − w · h), where W, H — dimensions of the outer rectangle and w, h — dimensions of the inner one (0 < w < W; 0 < h < H).
Write a program that finds a translation of one frame relative to another that results in maximum frames intersection area.
Input
Each frame is described by four points — two opposite corners of the outer rectangle, followed by two opposite corners of the inner rectangle. Points are described by their coordinates — pairs of integer numbers x and y. Coordinates do not exceed 10^8 by absolute value.
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.
Output
The first line of the output file must contain an integer number A — the maximal possible intersection area of the given two frames achievable by a translation.
The second line of the output file must contain a pair of integer numbers x and y — coordinates of the translation vector of the second frame that provides the intersection area A. Coordinates must not exceed 10^18 by the absolute value.
Example
input.txt
2 2 5 6 3 3 4 5
0 0 10 10 2 2 3 3
output.txt
10
1 1