A friend, who is a freshman in college, was recently complaining about a homework problem he was given in his computer science class. It took him four hours to complete, and challenged me to beat his time.

Ali has decided to build a giant, novelty analog clock, using large pieces of scrap metal that he found in the attic of his new house. He has several perfect triangular pieces that could be used as hands for the clock, but depending on the hands he selects, he is not sure he has a circular piece big enough to use for the clock face.

For each triangular metal piece used as a clock hand, he plans to attach a small hinge at the midpoint of the triangle’s shortest side. The hinge will attach the hand to the exact center of the clock face, which is a perfect circle.

The point of a hand is the corner of the triangle piece that is opposite its hinged side. The clock face needs to be large enough that the points of both hands will fit entirely within the circle.

Ali wants to be absolutely certain that the sharp points of the hands won’t protrude beyond the clock face, in spite of any in his original measurements or floating-point calculations. So, any point inside the circle that is calculated to be less than 0.01 meters from the circle’s edge should be considered outside the clock face.

(The entire problem can be found here.) The most complicated part of this is finding the length of the triangle. The length we need stretches from the middle of the shortest side to the opposite corner, forming a median of the triangle. The formula to find this length (called Apollonius’ Theorem) is as follows:

This is trivial to implement in C:

double medianlength(double a, double b, double c) {
return sqrt(2*b*b + 2*c*c - a*a) / 2;
}


The algorithm I use is rather simple. It reads the input file, and for each line it parses all six integers. For both groups of three it orders them from smallest to largest, and uses the above function to find the length of the median. This length is the radius of the circle. It chooses the larger of the two radii, rounds up to the nearest whole number, and doubles it. The resulting number is the diameter necessary for the clock.

It only took me around two hours to solve the problem, easily beating Dan’s time of four hours. The full source code for my solution can be found on GitHub.