p514.ans2
======================
4.4721359550


=================
p514.in3
======================
10
5 5 5 5 5 5 5 5 5 5

=================
p514.in2
======================
4
8 4 3 5

=================
p514.ans3
======================
0.0000000000

=================
p514.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
}

double area(int a, int b, int c) {
    double s = (a + b + c) / 2.0;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

double rec(int i, int x, int y, int z) {
    if(i == n) {
        if(x + y < z || y + z < x || z + x < y) {
            return 1e18;
        }
        return area(abs(x), abs(y), abs(z));
    }
    double res = 1e18;
    res = min(res, rec(i + 1, x + a[i], y, z));
    res = min(res, rec(i + 1, x, y + a[i], z));
    res = min(res, rec(i + 1, x, y, z + a[i]));
    res = min(res, rec(i + 1, x - a[i], y, z));
    res = min(res, rec(i + 1, x, y - a[i], z));
    res = min(res, rec(i + 1, x, y, z - a[i]));
    return res;
}

void solve() {
    // Fundamentally the solution is simple - we can notice n <= 10, so this
    // immediately suggests that we can use a brute force solution. The main
    // observations is that we should always aim for an area 0.0 polygon (e.g.
    // say if we have 5, 5, 5, and 5). If this is impossible, we should make a
    // triangle. We can note that we should always be able to make on of these
    // two. This idea generalizes - instead of sequentially attaching the sides,
    // we can make an area 0.0 zone as part of a side of the triangle, and
    // essentially get a "smaller" triangle. This leads to the idea of brute
    // forcing the sides of a triangle but we can move the sides in both
    // directions, positive meaning we extend the side, negative meaning we
    // create a zone with almost no area.

    cout << setprecision(10) << fixed << rec(0, 0, 0, 0) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p514.ans1
======================
6.0000000000


=================
p514.in1
======================
3
3 4 5

=================
statement.txt
======================
514. Polygon
Time limit per test: 1.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

You are given lengths of sides of some polygon. You must find the infimum of the possible areas of simple polygons with such side lengths. Infimum of a set of real numbers A is the exact upper bound of the set L of all real numbers y such that for any x ∈ A holds y ≤ x.

A simple polygon is a polygon without self-intersections and self-touchings.

Input
The first line contains integer n, 3 ≤ n ≤ 10 — the number of sides of the polygon. The second line contains n integers a1, a2,..., an, such that  for any 1 ≤ i ≤ n (this means that there exists a simple polygon with sides a1, a2,..., an. Also, 1 ≤ ai ≤ 100.

Output
Output one real number — the answer to the problem. Your answer will be considered correct if absolute or relative error is less than 10-6.

Example(s)
sample input
sample output
3
3 4 5
6.0000000000

sample input
sample output
4
8 4 3 5
4.4721359550

sample input
sample output
10
5 5 5 5 5 5 5 5 5 5
0.0000000000

=================
