Editorial for CCC '21 S1 - Crazy Fencing


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.

Author: Plasmatic

Observe that each fence piece is a trapezoid. We can loop through adjacent pairs of heights and use the width to calculate the area of each fence piece. The answer is the sum of areas of all fence pieces.

There are many ways to avoid precision issues with the problem, but one of them is to store 2 \times \text{answer} (which is guaranteed to be an integer) instead and divide by 2 at the end, printing .5 if necessary.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.