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
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.
{46,40,84,27}
Returns: 537.3680652029855
{31,44,83,44}
Returns: 638.2820203483724
{34,46,79,18}
Returns: 261.4478915577634
{36,26,19,63,28}
Returns: 361.68356335338217
{78,30,41,38,18}
Returns: 545.3686253351947
{95,59,37,33,11}
Returns: 554.3484351019672
{51,10,97,14,47,39}
Returns: 871.9559550229587
{29,19,62,21,36,2}
Returns: 304.47988439304163
{49,5,23,39,88,42}
Returns: 788.6190461813612
{83,10,10,22,18,80,10}
Returns: 923.3003824046832
{21,16,46,66,63,17,37}
Returns: 1516.5175802961414
{35,75,30,95,79,62,26}
Returns: 3256.099913851602
{31,80,23,71,77,26,53,6}
Returns: 2775.998799405252
{36,79,19,9,56,18,98,19}
Returns: 2361.8707096987278
{59,59,24,3,29,50,79,23}
Returns: 1999.133833435806
{35,96,1,40,93,92,48,47,89}
Returns: 4656.6253411395655
{12,18,86,1,31,14,15,61,36}
Returns: 1025.1328565808249
{89,26,100,29,28,55,69,2,8}
Returns: 3325.864736348445
{25,11,7,7,66,63,59,66,28,34}
Returns: 2194.9852819506395
{69,31,39,10,13,93,97,93,26,21}
Returns: 4299.274537154505
{32,63,84,70,60,76,31,21,91,74}
Returns: 5329.139041375465
{33,85,79,81,86,32,82,66,27,67,34}
Returns: 5979.244334419546
{26,30,52,17,83,27,92,70,92,60,89}
Returns: 5971.743274521125
{99,12,60,27,2,28,42,55,95,15,14}
Returns: 3415.878271852212
{13,20,75,15,100,33,55,18,21,1,82,23}
Returns: 3387.8236744757405
{18,57,22,100,42,38,44,42,40,36,19,36}
Returns: 1983.5036288151425
{52,90,29,58,5,12,11,85,91,96,18,71}
Returns: 5784.539696567363
{35,41,64,71,47,19,37,15,76,17,45,90,87}
Returns: 5340.800167856549
{70,98,53,28,69,12,4,74,99,27,1,25,70}
Returns: 5784.5545450188965
{78,49,6,85,60,72,100,38,7,14,54,77,8}
Returns: 6170.687321219386
{90,69,84,1,97,14,79,92,13,94,18,3,24,41}
Returns: 7026.020050110176
{8,29,73,97,74,7,27,8,70,51,46,15,94,51}
Returns: 5641.464086930983
{34,41,91,47,4,5,14,18,18,7,84,5,74,60}
Returns: 4010.0029482647806
{72,49,63,12,66,6,58,19,18,73,61,52,53,81,31}
Returns: 5591.935769507378
{19,95,13,83,100,75,40,14,89,69,10,23,81,30,13}
Returns: 7021.362282513253
{52,17,37,19,58,96,45,49,2,35,19,9,80,58,65}
Returns: 4863.0840473486005
{21,72,15,55,16,44,54,63,69,35,75,69,76,70,50,81}
Returns: 7512.322360676162
{32,17,99,92,84,42,1,68,17,91,4,35,10,69,43,18}
Returns: 6888.94807319841
{60,69,84,9,42,51,61,10,18,64,37,88,7,58,89,44}
Returns: 7171.136238054464
{98, 99, 100, 97, 46, 47 }
Returns: 4450.281542411054
{1, 2, 3, 5, 8, 13, 14, 14, 14 }
Returns: 86.1617850785388
{21, 72, 15, 55, 16, 44, 54, 63, 69, 35, 75, 69, 76, 70, 50, 81 }
Returns: 7512.322360676162
{1, 11, 11, 11, 11, 10 }
Returns: 54.48411009962254
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
Returns: 2.1650635094610964
{27, 50, 78, 82, 82, 82 }
Returns: 3005.1672676600683
{7, 19, 26, 26, 27, 29 }
Returns: 339.00335608860416
{10, 10, 20, 20, 21, 21 }
Returns: 198.80497392704112
{4, 90, 97, 5, 97, 98, 95 }
Returns: 4111.888641079868
{21, 72, 11, 55, 16, 44, 54, 99, 69, 35, 71, 69, 76, 70, 50, 81 }
Returns: 8070.4353454215725
{100, 99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85 }
Returns: 18760.274805567216
{3, 9, 6, 18, 13, 24, 1, 30, 25, 94, 7, 34, 56, 12, 24, 15 }
Returns: 815.9852508137787
{100, 100, 90, 90, 45, 45 }
Returns: 4153.005036881826
{7, 4, 4, 4 }
Returns: 6.928203230275509
{1, 2, 3, 3, 3, 3 }
Returns: 4.3074470705210945
{21, 72, 15, 55, 16, 44, 54, 63, 69, 35, 75, 69, 76, 70, 80, 81 }
Returns: 8106.584104885184
{99, 99, 89, 89, 44, 44 }
Returns: 4020.778320035727
{23, 78, 32, 41, 75, 89, 78, 63, 74, 66, 4, 56, 7, 8, 9, 4 }
Returns: 6209.683602402974
{11, 11, 10, 10, 7, 3 }
Returns: 51.32943377553876
{21, 72, 100, 55, 16, 44, 54, 55, 55, 35, 75, 69, 76, 100, 1, 81 }
Returns: 8770.257887112295
{10, 1, 1, 1 }
Returns: 0.4330127018922193
{99, 100, 98, 98, 98, 100, 97, 90, 90, 70, 71, 72, 68, 1, 2, 3 }
Returns: 14318.600013502903
{3, 4, 5, 6, 7, 8, 9, 6, 6, 6, 6, 6, 6, 6, 6, 5 }
Returns: 82.76333892426885