Bubbly Troubly

This problem asks us to simulate the filling of a champagne tower with arbitrarily placed glasses.

We need to calculate where water will go when any given glass is full. Since water falls down, we'll do this in descending z order. for each glass, look at the glasses above it and evaluate the circles for any intersection. if there is, the amount of water that goes into this glass relative to the total water in the above glass is proportional to how much the circumference of the upper glass overlaps relative to the total circumference. We track the contribution from each glass above us.

Caveat: what if there is a glass between us and some higher glass which is "stealing" some of the overflow? Maintain a list of segments of "unused" portions of each glass, that is, the range of angles which, were there no more glasses, would be dumping water onto the floor. The rest of the water is currently being "consumed" by some other glass between, so we can only take the water falling from the unused portions. Modify the ranges accordingly. Clever ones can use a segment tree for this, but as there are 20 glasses, it is not necessary.

Once the graph of consumers is completed, simulate the fill. The maximum time is too large (10^8 centiseconds) to go timestep by timestep, so we have to figure out the next "interesting" thing occurs, namely when a glass fills next. This means we need to store total volume of each glass, and the current fill rate. Each time a glass fills, we update our fill rates based on the previously calculated values, and then calculate which glass will fill up next.

If there is any glass other than the top glass that has no "filler," the problem is impossible.