TopCoder problem "Curvy" used in TCO07 Semi 2 (Division I Level One)



Problem Statement

    A road consists of a sequence of circular arcs and straight sections. We want to know the straight line distance between the two ends of the road, treating the road as a curvy line with negligible width.

The path of the road is specified by a sequence of sections. Each section has a length (when travelling along the road) and a radius of curvature (telling the radius of a circle that this section follows). A positive radius is a curve to the right, a negative radius indicates that the curve is to the left, and a radius of 0 is a special value indicating that this section is straight.

Each circular arc section of the road is on the circle that is tangential to the path of the road at both its ends. So, for example, if the road is heading northeast when a section with radius of curvature equal to -3 begins, the center of that section's circle is 3 units to the northwest of that point on the road.

Create a class Curvy that contains a method distance that is given int[]s length and radius and that returns the straight line distance between the two ends of the road. The i-th elements of length and radius indicate the information for the i-th section as we travel from start to end.

 

Definition

    
Class:Curvy
Method:distance
Parameters:int[], int[]
Returns:double
Method signature:double distance(int[] length, int[] radius)
(be sure your method is public)
    
 

Notes

-A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
 

Constraints

-length will contain between 1 and 50 elements, inclusive.
-radius will contain the same number of elements as length.
-Each element of length will be between 1 and 10,000, inclusive.
-Each element of radius will be between -100 and 100, inclusive.
 

Examples

0)
    
{100}
{0}
Returns: 100.0
This road is a single section which is straight and has a length of 100.
1)
    
{628}
{-1}
Returns: 0.3171858120571965
This road is a single section which curves to the left with a radius of curvature of 1. It goes around in a circle on top of itself almost exactly 100 times, so its two ends are pretty close to each other.
2)
    
{628,50,20,10}
{1,0,0,0}
Returns: 79.68684435034164
This road is composed of 4 sections. The first section behaves as in the previous example except it curves to the right. Then, in 3 separate straight sections, the road continues in a straight line for 50+20+10 = 80 units.

628 is a bit smaller than (2*PI) * 100. This means that after going 628 units along the circle, the road will be headed nearly toward the starting point. The final 3 sections continue on 50+20+10 = 80 units in that direction, so the final distance from the start to the end is a little less than 80.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6668

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10840&pm=6668

Writer:

dgoodman

Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy , ivan_metelsky

Problem categories:

Geometry