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)
    • Let us define v(h) = volume of a cone with height h going through point (x, y, z). This function can be computed with some basic geometry
    • Function v(h) is convex
  • For n points the volume is \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 can be found using volume and h

Comments

There are no comments at the moment.