TopCoder problem "GrasslandFencer" used in SRM 314 (Division I Level Two , Division II Level Three)

Problem Statement

There is a large grassland next to the villa Pemberley in the southern region of Byterland. Mrs. Darcy is afraid of her potted plants being trampled by strangers, so she decides to fence in some triangular areas in the grassland.

Mrs. Darcy has several fences in her basement. She will form each triangular area using exactly three fences, such that each side of the triangle is a single fence. Since the fences are beautifully decorated, she will not glue multiple fences together to form a single side, or split a single fence into multiple smaller fences. Her goal is to fence in as large an area as possible.

You are given a int[] fences containing the lengths of Mrs. Darcy's fences. Return the maximal area that can be fenced in.

Definition

Class:	GrasslandFencer
Method:	maximalFencedArea
Parameters:	int[]
Returns:	double
Method signature:	double maximalFencedArea(int[] fences)
(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.

With three fences of length A, B, and C, where A <= B <= C, a triangle can be constructed if and only if A + B > C.

The area of a triangle with side lengths A, B, and C is sqrt(p*(p-A)*(p-B)*(p-C)), where p = (A+B+C)/2."

Constraints

fences will contain between 1 and 16 elements, inclusive.

Each element of fences will be between 1 and 100, inclusive.

Examples

{3,4,5,6,7,8,9}

Returns: 36.754383146489694

You can construct two triangles (3, 4, 5) and (7, 8, 9) with a total area of approximately 32.83 square meters. This is a preferable solution to constructing triangles (4, 5, 6) and (7, 8, 9), which have a total area of approximately 36.75 square meters.

{1,2,4,8}

Returns: 0.0

Can not form any triangle here.

{7,4,4,4}

Returns: 6.928203230275509

Duplicate elements in fences are allowed.

{21,72,15,55,16,44,54,63,69,35,75,69,76,70,50,81}

Returns: 7512.322360676162

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9994&pm=6467

Writer:

zhuzeyuan

Testers:

PabloGilberto , brett1479 , Olexiy , Andrew_Lazarev