Frames
Time limit3sMemory limit256 MB
Given two axis-aligned picture frames (outer rectangle minus inner rectangle), find the translation of the second frame maximizing the intersection area with the first.
- Level
Hard8 of 10
- Topics
- Geometry, Math, Brute force
- Solved
- No attempts yet
Problem
Vasya and Petya are playing an interesting game. The rules are simple: there are two frames, and a player must translate the second frame so that the area of the intersection of the two frames is as large as possible. Each player writes down a translation vector for the second frame, and whoever achieves the larger intersection area wins.
Vasya wants to win by writing a program that finds the best translation vector.
In this game a frame is the difference of two rectangles: an outer rectangle minus an inner rectangle. The inner rectangle lies strictly inside the outer one (its boundary never touches the outer boundary), and the sides of both rectangles are parallel to the coordinate axes.
To make the definition clearer, consider a few examples.
The area of a frame is , where are the dimensions of the outer rectangle and are the dimensions of the inner one (, ).
Write a program that finds the maximum possible intersection area of the two frames achievable by translating the second frame.
Input
Each frame is described by four points: two opposite corners of the outer rectangle, followed by two opposite corners of the inner rectangle. Each point is given by its integer coordinates and . All coordinates do not exceed in absolute value.
The first line contains the description of the first frame. The second line contains the description of the second frame.
Output
Print a single integer — the maximum intersection area of the two frames achievable by translating the second frame.


