TopCoder problem "InscribedTriangles" used in SRM 326 (Division I Level Two)



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

Writer:

jmzero

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Geometry