Thursday, December 18, 2014



TopCoder Problem Statement - Archimedes


Approximate the value of Π using the circumference of polygons inscribed in a circle.

Java Source:
01: public class Archimedes {
03:     public double approximatePi(int numSides) {
05:         double innerAngle = 360 / (double) numSides;
06:         double outerAngle = (180 - innerAngle) / 2;
08:         // Don't forget to convert to Radians 
09:         double lengthOfSide = Math.cos(Math.toRadians(outerAngle));
11:         return numSides * lengthOfSide;
13:     }
14: }

To solve this, we need to determine the length of each side of the inscribed polygon.

To construct the inscribed polygon, start by imagining spokes coming from the center of the circle out to the edge. The number of spokes equals the number of sides in the polygon. The polygon will be drawn by connecting the points where the spokes intersect the circle.

Next, the angle between the spokes is simply 360° divided by the number of spokes (sides). I've called this innerAngle.

outerAngle is the angle formed between a spoke and a side of the inscribed polygon. Since two adjacent spokes and the connecting edge between them constitute a triangle, the sum of their interior angles is 180° Therefore, outerAngle is 180° - innerAngle divided by 2.

Now, the length of the side of the polygon is just the cosine of the outerAngle. Note that Math.cos() expects a value in radians, so remember to call Math.toRadians() first since we've been working in degrees.

Finally, just return numSides * lengthOfSide.

Be careful to cast to a double where necessary in order to avoid losing precision. You will not get the correct answer if the cast is left out of the calculation for the innerAngle.

If you need to brush up on your trigonometry, there are plenty of sites to help out. I recommend checking out the Kahn Academy

As a final note, the TopCoder editorials given an even shorter answer:

  • return numSides * Math.sin(Math.PI / numSides);
I'm not sure how I feel about using Math.PI when we're trying to approximate Π but I supposed that's being picky. Besides, I'm sure the toRadians() method uses Π anyway.

No comments:

Post a Comment