Editorial for COCI '08 Contest 2 #1 Kornislav

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

The solution is to sort the numbers $A$ ~A~, $B$ ~B~, $C$ ~C~ and $D$ ~D~ and output the product of the first and third numbers.

We need to separate the four numbers into two sets, one containing horizontal moves $\{x_1, x_2\}$ ~\{x_1, x_2\}~, the other containing vertical moves $\{y_1, y_2\}$ ~\{y_1, y_2\}~. The area is then $\min(x_1, x_2) \cdot \min(y_1, y_2)$ ~\min(x_1, x_2) \cdot \min(y_1, y_2)~. This expression is maximized when the two smallest numbers are in the same set.

Comments

There are no comments at the moment.