This page is still under construction.

Parts of this page are still being built. What you see may change.

Fruit Bowl

Time limit1sMemory limit128 MB

Summary
Given a V-shaped bowl with left and right wall angles and height H, simulate greedily dropping unit circles to find how many fit below the rim.
Level

Medium7 of 10

Topics
Geometry, Simulation, Greedy
Solved
No attempts yet

Problem

For her next project, Beebe Flat wants to paint a bowl of fruit. Naturally, the bowl is two-dimensional, and so is all of the fruit. She bought a triangular bowl that somehow always stays upright, with a perfectly level top. The bowl has height HH, and it opens AA degrees to the left and BB degrees to the right (see the diagram). For the sake of art, Beebe avoids symmetry, so A≠BA \ne B.

She plans to buy perfectly circular fruit, each with radius 11, to place into the bowl. Because perfectly circular fruit is expensive, she needs your help to work out how much fruit she has to buy. She fills the bowl to the brim, adding as much fruit as possible without any part rising above the top of the bowl. She is not interested in optimal packing, since she wants a simple rule for arranging the fruit: she places the fruit one at a time, and each time she chooses the lowest possible position for the center.

Because Beebe dislikes ties, she always buys a bowl for which there is only one lowest possible position, within a margin of 10−510^{-5}. Finally, so that a lid will fit nicely once she is done painting, she only chooses bowls such that, when packed this way, the last piece of fruit that fits sits at least 10−210^{-2} below the top, and the next piece that would fit if the bowl were taller would stick out at least 10−210^{-2} above the top.

Given a particular bowl, how many pieces of fruit does Beebe need to buy to fill it in this manner?

Input

The input consists of multiple test cases. Each test case is a single line with three integers AA, BB, and HH, where 1≤A,B≤451 \le A, B \le 45, A≠BA \ne B, and 1≤H≤3001 \le H \le 300. The last line contains A=B=H=0A = B = H = 0 and must not be processed.

Output

For each test case, print on its own line the number of pieces of fruit Beebe must buy to fill the given bowl.

Examples2

  1. Example 1

    Input
    20 30 10
    10 20 20
    0 0 0
    
    Expected output
    9
    25
    
  2. Example 2

    Input
    45 1 25
    0 0 0
    
    Expected output
    72