Editorial for ICPC NEERC 2010 D - Dome of Circus

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.

Assume we have a single point $(x, y, z)$ ~(x, y, z)~
- Let us define $v(h) =$ ~v(h) =~ volume of a cone with height $h$ ~h~ going through point $(x, y, z)$ ~(x, y, z)~. This function can be computed with some basic geometry
- Function $v(h)$ ~v(h)~ is convex
For $n$ ~n~ points the volume is $\max(v(h))$ ~\max(v(h))~.
- It is also a convex function
- The optimal dome's volume for the problem is the min of this function
- It can be found using ternary search
- The radius $r$ ~r~ can be found using volume and $h$ ~h~

Comments

There are no comments at the moment.