410562: GYM104052 A Sheet Metal
Description
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.
InputThe 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.
OutputPrint the minimum possible area of the largest remaining piece.
ScoringSubtask | Point | Constraints |
1 | 50 | $$$w_2 \le h_2 \le w_1 \le h_1$$$ |
2 | 50 | No additional constraints |
2 3 1 3Output
1.5Input
2 3 3 3Output
0Input
2 3 2 2Output
1Input
2 3 3 1Output
1.5