1526. Grassland Fence

Near Pemberley Villa, located in the southern district of Byteland, there is a large pasture. Mrs. Darcy is concerned about her delicate plants, which could be trampled by strangers. Therefore, she decided to enclose certain areas of the pasture with triangular fences.

In Mrs. Darcy’s basement, there are several fences. She forms each triangular area using exactly three fences, so that each side of the triangle corresponds to one fence. The fences are sturdy and beautiful, so she will not combine multiple fences to form a single side, nor will she cut a fence into shorter pieces. Mrs. Darcy’s goal is to enclose the largest possible total area of the pasture.

Input. Each line contains a separate test case. The first number in the line is the number of fences n (n ≤ 16) that Mrs. Darcy has. The next n integers, each between 1 and 100, are the lengths of these fences.

Output. For each test case, print in a separate line the maximum area that can be enclosed using the available fences. The answer must be printed with 4 decimal digits.

Sample input	Sample output
7 3 4 5 6 7 8 9 4 1 2 4 8 4 7 4 4 4	36.7544 0.0000 6.9282

SOLUTION

dynamic programming - masks

Algorithm analysis

The area of a triangle with sides a, b and c is computed in the function area using Heron’s formula:

S = , where p =

Let P be some subset of the available fence pieces. The function FindSol(mask) finds the maximum area that can be enclosed using triangles formed from the pieces in this subset.

The variable mask represents a subset mask: it is a 16-bit number whose i-th bit is equal to 1 if the subset P contains the piece fences[i], and 0 otherwise.

The answer to the problem is the value FindSol(2ⁿ – 1), where n is the number of elements in the array fences.

The values of all possible masks mask lie in the range from 0 to 2¹⁶ – 1 (since, according to the constraints, there are no more than 16 fence pieces). The array entry best[mask] stores the maximum area that can be enclosed by the subset of fence pieces corresponding to the mask mask.

To compute FindSol(mask), all possible triples of fence pieces i, j, k that are present in mask should be enumerated. For each triple, the triangle inequality is checked to ensure that a triangle can be formed from these pieces. If a triangle is possible, the following sum is computed:

area(fences[i], fences[j], fences[k]) + FindSol(mask \ {i, j, k})

Next, all such triples (i, j, k) are considered, and the one for which this sum is maximal is selected. This maximum value is assigned to best[mask]:

FindSol(mask) =

If the lengths of the fence pieces are initially sorted, then when checking the triangle inequality (for a triangle with sides fences[i], fences[j], fences[k]), it is sufficient to check only one condition:

fences[i] + fences[j] > fences[k]

Since after sorting we have

fences[i] £ fences[j] £ fences[k],

it always follows that

fences[i] + fences[k] > fences[j] и fences[j] + fences[k] > fences[i].

Example

In the first test, the optimal triangles to construct have sides (4, 5, 6) and (7, 8, 9). The total enclosed area in this case is 36.7544.

In the second test, the answer is 0, since no triangle can be formed from the available fences.

In the third test, a triangle with sides (4, 4, 4) should be constructed. Note that fence lengths can be repeated.

Algorithm implementation

Declare the global variables.

#define MAX 16

double best[1<<MAX];

int f[MAX+1];

The function area computes the area of a triangle using Heron’s formula.

double area(int a, int b, int c)

{

double p = (a + b + c) / 2.0;

return sqrt(p * (p - a) * (p - b) * (p - c));

}

The function FindSol returns the maximum area that can be enclosed using triangles formed from the fences included in the mask mask.

double FindSol(int mask)

{

If the value in the array best[mask] is greater than or equal to zero, it has already been computed, and the function returns this value. This avoids redundant computations and speeds up the algorithm.

if (best[mask] >= 0.0) return best[mask];

Initialize best[mask] = 0.

best[mask] = 0;

Iterate over all possible triples of indices (i, j, k) such that the corresponding fences are included in mask.

for (int i = 0; i < n - 2; i++) if (mask & (1 << i))

for (int j = i + 1; j < n - 1; j++) if (mask & (1 << j))

for (int k = j + 1; k < n; k++) if (mask & (1 << k))

Check the triangle existence condition. Since the fences are initially sorted, this condition is sufficient to ensure that a triangle can be formed.

if (f[i] + f[j] > f[k])

If the triangle exists, compute the sum:

· the area of the current triangle area(f[i], f[j], f[k]);

· plus the maximum area that can be enclosed with the remaining fences, excluding those used in this triple:

FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k))

best[mask] = max(best[mask], area(f[i],f[j],f[k]) +

FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)));

return best[mask];

}

The main part of the program. Read the number of fences n.

while (scanf("%d",&n) == 1)

{

memset(f,0,sizeof(f));

Read the lengths of the fences and sort them in non-decreasing order.

for (i = 0; i < n; i++) scanf("%d",&f[i]);

sort(f,f + n);

Initialize the array best.

for (i = 0; i < (1 << MAX); i++) best[i] = -1.0;

Compute and print the answer.

printf("%.4lf\n",FindSol((1 << n) - 1));

}