Problem Statement

A triangle is "inscribed" in a circle if all 3 points of the triangle are on the edge of the circle. For this problem, our circle will be centered at the origin and have a radius of 5. Our goal is to find the largest triangle (by area) we can inscribe in this circle. Normally, this would be any equilateral triangle, but in this case we have the added restriction that each point of our triangle must be within one (or more) of the valid ranges of degrees. The degree ranges are given in thousandths of degrees in corresponding elements of angleFrom and angleTo. For each range, angleFrom will be less than or equal to angleTo and each will be between 0 and 360000. All ranges are inclusive; see the examples for clarification. Return the area of the largest inscribed triangle that can be made while following these restrictions. If no triangle can be made, return 0.

Definition

 Class: InscribedTriangles Method: findLargest Parameters: int[], int[] Returns: double Method signature: double findLargest(int[] angleFrom, int[] angleTo) (be sure your method is public)

Notes

-The ranges may overlap.
-Your return value must have an absolute or relative error less than 1e-9.

Constraints

-angleFrom and angleTo will each contain between 1 and 30 elements, inclusive.
-angleFrom and angleTo will contain the same number of elements.
-Each element of angleFrom and angleTo will be between 0 and 360000, inclusive.
-Each element of angleFrom will be less than or equal to the corresponding element of angleTo.

Examples

0)

 {0} {360000}
Returns: 32.47595264191645
 We can use any point we want on the circle - so we can draw an equilateral triangle (which will be the biggest we can ever draw).
1)

 {15000,25000,100000,265000,330000} {15000,25000,100000,265000,330000}
Returns: 27.433829549752186
 In this case, each of our ranges are single points. The biggest triangle can be made by using the points at 15°, 100°, and 265°.
2)

 {245900,246500,249900} {245915,246611,252901}
Returns: 0.002789909594714814
 We only have 3 small ranges, all near to each other - so our best triangle is still really small.
3)

 {42} {42}
Returns: 0.0
 It's hard to draw a triangle with one point.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10006&pm=6730

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Geometry