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.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Assume we have a single point
- Let us define volume of a cone with height going through point . This function can be computed with some basic geometry
- Function is convex
- For points the volume is .
- 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 can be found using volume and
Comments