|
|
For each possible triangulation, compute the smallest area triangle in it.
Print the largest smallest area triangle.
If that does not make much sense, let's go over the sample input:
The given quadrilateral can be triangulated in only two different ways. The areas of the resulting triangles are:
Cut #1: 11.5 + 16.0 (min. area triangle = 11.5)
Cut #2: 10.0 + 17.5 (min. area triangle = 10.0)
answer = max(11.5, 10.0) = 11.5
Good luck! I'm native Russian language speaker, but I really cannot understand what is required in the problem:
"Поскольку Вадим не любит сладкое, в конце он выберет себе самый маленький по площади кусочек, однако он не хочет, чтобы кто-то это заметил. Для этого современному обер-форшнейдеру нужно подобрать такой способ элегантно разделить торт, чтобы часть, которая достанется ему, была наибольшего размера."
He doesn't like sweets, so he takes part of minimal size, but he wants to maximize size at the same time. WTF, where is the logic here, what does author want from us - to find maximin over all cuts, or something else? |
|
|
