GrasslandFencer
SRM 314 · 2006-08-03 · by zhuzeyuan
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
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.
{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.
{46,40,84,27}
Returns: 537.3680652029855
{31,44,83,44}
Returns: 638.2820203483724
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GrasslandFencer with a public method double maximalFencedArea(vector<int> fences) · 65 test cases · 2 s / 256 MB per case