410562: GYM104052 A Sheet Metal

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Sheet Metaltime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

James has a large rectangular piece of sheet metal; its width is $$$w_1$$$ millimeters, and its height is $$$h_1$$$ millimeters. This massive piece is hard to store and move around, so James and his friends want to make smaller pieces.

They found a machine that could solve this problem. The machine has a rectangular form of width $$$w_2$$$ and height $$$h_2$$$ millimeters. To use it, you put a piece of sheet metal under the form. It's allowed to have some parts of the form not be above the sheet metal. You can rotate the piece of sheet metal, but you have to make sure that the sides of both rectangles (the piece and the form) are parallel to coordinate axes.

After running the machine, everything under the form will get burnt out and be unusable. Everything that was not under the form will fall off; James and his friends must take that away with them. In addition, the remaining part might will apart into several separate pieces. If the form's edge coincides with the sheet metal's edge, we also consider that the sheet metal is disconnected there.

To ease the task of taking everything away, find a way to apply the machine to the piece of sheet metal such that the maximum area of all remaining pieces is as small as possible. In case there are no pieces left, print 0.

Input

The only line of the input contains four integers $$$w_1$$$, $$$h_1$$$, $$$w_2$$$, $$$h_2$$$ ($$$1 \le w_1, h_1, w_2, h_2 \le 10^6$$$) — widths and heights of the piece of sheet metal and the form.

Output

Print the minimum possible area of the largest remaining piece.

Scoring
SubtaskPointConstraints
150$$$w_2 \le h_2 \le w_1 \le h_1$$$
250No additional constraints
ExamplesInput
2 3 1 3
Output
1.5
Input
2 3 3 3
Output
0
Input
2 3 2 2
Output
1
Input
2 3 3 1
Output
1.5

加入题单

上一题 下一题 算法标签: