(As far as I can see, the online competition is now over, so I shall reinstate my answer as promised.)
As commented by hardmath, and agreed by the OP, the solution is a cyclic polygon whose vertices lie on a common circle.
Note that if one of the line segments would be longer than the sum of the length of the rest of the line segments, they cannot form a polygon. Because of this, we know that
$$L_i \le \sum_{k \ne i}^{n} L_k$$
for all $i = 1 \ldots n$. (This also means that $0 \le \theta_i \lt \pi$.)
Each of the $n$ line segments essentially forms an isosceles triangle with the center of the common circle. Two of the sides are of length $r$, the radius of the common circle, and the third is the line segment itself, length $L_i$. (Essentially, we can decompose the polygon into triangular wedges, each being an isosceles triangle. This also means that the order of the line segments does not affect the area, as reordering the triangular parts does not change their areas.)
The length of a circular chord fulfills
$$L_i = 2 r \sin\left(\frac{\theta_i}{2}\right)$$
Here, $\theta_i$ is the angle between the $r$-length edges in the isosceles triangles. Solving for $\theta_i$, we see that
$$\theta_i = 2 \arcsin \left( \frac{L_i}{2 r} \right) = \arccos \left( 1 - \frac{ L_i^2 }{2 r^2} \right)$$
because $2 \arcsin(x) = \arccos(1 - 2 x^2)$ when $0 \le x \le 1$.
Note that this also means that
$$\frac{d \, \theta_i}{d \, r} = - \frac{2 L}{\sqrt{4 r^4 - L^2 r^2}}$$
In order for the figure to be a polygon, the sum of the angles $\theta_i$ must equal $180°$:
$$\sum_{i=1}^{n} \theta_i = 2 \pi$$
Combining the above two, and dividing by two, we get
$$\sum_{i=1}^{n} \arcsin \left( \frac{L_i}{2 r} \right) = \pi$$
which we can use to numerically solve for $r$.
In order for each $\theta_i$ to exist, $\max(L)/(2r) \le 1$. This means that $r \ge \max(L)/2$, and that $r_{min} = \max(L)/2$ is the minimum allowed radius in the numerical methods.
We also know that the radius must be less than half the perimeter, so $r_{max} = (\sum_i L_i) / 2$.
When we have found the $r$ for which $\sum_i \theta_i = 2 \pi$, we can compute the vertex coordinates. Since the points are to be in clockwise order, we can use
$$\begin{cases}
x_i' = x_0 - r \cos \varphi_i \\
y_i' = y_0 + r \sin \varphi_i \\
\end{cases}$$
where
$$\begin{cases}
x_0 = r \cos \varphi_1 \\
y_0 = -r \sin \varphi_1
\end{cases}$$
and
$$\varphi_i = \begin{cases}
-\frac{\theta_i}{2}, & i = 1 \\
-\frac{\theta_i}{2} + \sum_{k=1}^{i-1} \theta_i, & 2 \le i \le n
\end{cases}$$
The above gives us $\varphi_1 = -\theta_1/2$ and $\varphi_2 = -\varphi_1 = \theta_1/2$, so the first line segment will be vertical; $x_1 = x_2 = y_1 = 0$, $y_2 \gt 0$ (in fact $y_2 = L_1$).
The above therefore yields $x_1 = 0$, $y_1 = 0$, $x_2 = 0$, $y_2 = L_1$, with the rest of the vertices $(x_i, y_i)$ in clockwise order around the center at $(x_0, y_0)$.
Here is an example program that reads line lengths from standard input, and uses a binary search to find the radius with at least six digits of precision, outputting the vertex coordinates to standard output. example.c:
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define PI 3.141592653589793238462643383279502884197
#define TWO_PI 6.283185307179586476925286766559005768394
double theta(const double L, const double r)
{
return 2.0 * asin(0.5 * L / r);
}
double d_theta(const double L, const double r)
{
const double r2 = r * r;
return -2.0 * L / (r2 * sqrt(4.0 - L * L / r2));
}
double find_radius(const double length[], const size_t count, const double epsilon, size_t *iteration_count)
{
const double min_theta = 1.0 - epsilon;
const double max_theta = 1.0 + epsilon;
double sum_length = length[0];
double max_length = length[0];
double min_radius, radius, max_radius;
size_t iterations = 0;
size_t i;
for (i = 1; i < count; i++) {
sum_length += length[i];
if (max_length < length[i])
max_length = length[i];
}
min_radius = 0.5 * max_length;
max_radius = 0.5 * sum_length;
while (1) {
double sum_theta = 0.0;
iterations++;
radius = (0.5 * min_radius) + (0.5 * max_radius);
for (i = 0; i < count; i++)
sum_theta += theta(length[i], radius);
sum_theta /= TWO_PI;
if (sum_theta >= min_theta && sum_theta <= max_theta)
break;
else
if (sum_theta < 1.0)
max_radius = radius;
else
min_radius = radius;
}
if (iteration_count)
*iteration_count = iterations;
return radius;
}
int main(void)
{
double *line_length = NULL;
size_t line_count = 0;
size_t line_maxcount = 0;
double radius, phi, x, y, x0, y0;
size_t i;
/* Read line lengths from standard input. */
while (1) {
char buffer[1024], *line;
double length;
line = fgets(buffer, sizeof buffer, stdin);
if (!line)
break;
if (sscanf(line, " %lf", &length) < 1)
break;
if (length <= 0.0)
break;
if (line_count >= line_maxcount) {
const size_t maxcount = (line_count | 255) + 257;
double *temp;
temp = realloc(line_length, maxcount * sizeof line_length[0]);
if (!temp) {
fprintf(stderr, "Out of memory.\n");
return EXIT_FAILURE;
}
line_length = temp;
line_maxcount = maxcount;
}
line_length[line_count++] = length;
}
/* Verify sanity. */
if (line_count >= 3) {
double max_length = line_length[0];
double sum_length = line_length[0];
for (i = 1; i < line_count; i++) {
sum_length += line_length[i];
if (max_length < line_length[i])
max_length = line_length[i];
}
if (max_length > sum_length - max_length) {
fprintf(stderr, "Not a valid polygon; one of the line segments is too long.\n");
return EXIT_FAILURE;
}
} else {
fprintf(stderr, "Need at least three line lengths.\n");
return EXIT_FAILURE;
}
fprintf(stderr, "Read %zu line lengths:\n", line_count);
for (i = 0; i < line_count; i++)
fprintf(stderr, "\t%.6f\n", line_length[i]);
radius = find_radius(line_length, line_count, 0.0000002, &i);
fprintf(stderr, "radius = %.6f using %zu iterations.\n", radius, i);
phi = -0.5 * theta(line_length[0], radius);
x0 = radius * cos(phi);
y0 = -radius * sin(phi);
for (i = 0; i < line_count; i++) {
x = x0 - radius * cos(phi);
y = y0 + radius * sin(phi);
phi += theta(line_length[i], radius);
printf("%.6f %.6f\n", x, y);
}
return EXIT_SUCCESS;
}
Compile it using e.g. in Linux
gcc -Wall -O2 example.c -lm -o example
and run it, generating say 10 random line lengths as input, using
awk 'BEGIN { srand(); for (i=0; i<10; i++) printf "%.6f\n", 10.0*rand() }' | ./example
Here is an example of the output, first 12 lines to standard error, followed by 10 lines to standard output:
Read 10 line lengths:
1.487793
5.241667
2.002344
4.271945
7.815320
5.452837
6.012328
7.506031
3.599992
1.636063
radius = 7.377844 using 19 iterations.
0.000000 0.000000
0.000000 1.487793
2.346549 6.174880
3.990793 7.317614
8.195604 8.071990
14.300092 3.191984
14.080471 -2.256429
9.609570 -6.276271
2.286102 -4.630880
0.344424 -1.599406
Best Answer
After breaking my head for a few hours, i figured out the solution.
It is a dynamic programming problem:
Let $dp(m,o,r)$ denote the maximum area $r$-gon such that the starting vertex is $m$ and the ending vertex is $o$.
Then recurrence relation will be:
$dp(m,o,r) = \max\limits_{\forall n: \lbrace m<n<o \rbrace} (dp(m,n,r-1) + area(m,n,o))$
where $area(m,n,o)$ is the area of the triangle formed by vertices $m$,$n$ and $o$