#include <iostream>
#include <vector>
#include <cmath>


const int INF = 1000000000; // значение "бесконечность"
const int terminals = 7; // количество терминальных вершин
const int all = 2 * terminals; / количество всех вершин
const int MOD = 20;

using namespace std;
/*
struct mystruct{ //трехмерные точки с евклидовой нормой
    int x, y, z;
    mystruct(int x = 0, int y = 0, int z = 0) {}
    void gen() {
        x = rand() % MOD;
        y = rand() % MOD;
        z = rand() % MOD;
    }
};

double dist(mystruct a, mystruct b){
    return sqrt(pow(a.x - b. x, 2.) + pow(a.y - b. y, 2.) + pow(a.z - b.z, 2.));
}*/


struct mystruct{
    int x, y;
    mystruct(int x = 0, int y = 0) {}
    void gen() {
        x = rand() % MOD;
        y = rand() % MOD;
    }
};

double dist(mystruct a, mystruct b){
    // return sqrt(pow(a.x - b.x, 2.) + pow(a.y - b.y, 2.) ); евклидова норма для двумерных точек
    return max(abs(a.x - b.x), abs(a.y - b.y)); // норма по модулю максимума
}



double weithTree(vector < vector <double> > &g) { //мин. остовное дерево
    const int n = g.size();
// алгоритм

    double ans = 0;
    vector<bool> used (n);
    vector<int> min_e (n, INF), sel_e (n, -1);
    min_e[0] = 0;
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j=0; j<n; ++j)
            if (!used[j] && (v == -1 || min_e[j] < min_e[v]))
                v = j;
        if (min_e[v] == INF) {
            cout << "No MST!";
            return 0;
        }

        used[v] = true;
        if (sel_e[v] != -1)
           // cout << v << " " << sel_e[v] << " " << g[v][sel_e[v]] << endl;
            ans += g[v][sel_e[v]];

        for (int to=0; to<n; ++to)
            if (g[v][to] < min_e[to]) {
                min_e[to] = g[v][to];
                sel_e[to] = v;
            }
    }

    return ans;
}

vector <mystruct> gen () { // генерация вершин
    vector <mystruct> ans(all);
    for (int i = 0; i < all; ++i) {
        ans[i].gen();//make_pair(rand() % MOD, rand() % MOD);
    }
    return ans;
}

vector< vector<double> > makeG(vector <mystruct> &map) { //делаем матрицу смежности из вершин на входе
    const int n = map.size();
    vector<vector<double> > g(n, vector<double> (n));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            g[i][j] = dist(map[i], map[j]);
        }
    }
    return g;
}

double getOnly(vector<int> only, vector <mystruct> &map) { //ищем мин. ост. дерево на выбранных вершинах
    vector <mystruct> postMap;
    for (auto it = only.begin(); it != only.end(); ++it)
        postMap.push_back(map[*it]);
    vector < vector <double> > g = makeG(postMap);
    return weithTree(g);
}

vector<int> intToArray(int num){         // так как все терминальные вершины находятся в начале, то
    vector<int> a;                      //  мы всегда их берем в подмножество вершин
    for (int i = 0; i < terminals; ++i)
        a.push_back(i);
    int j = terminals;
    while (num > 0) {
        if (num % 2 == 1)
            a.push_back(j);
        num /= 2;
        ++j;
    }
    return a;
}


double solve(){ //переберем все подмножества и выберем лучшее
    int subterm = all -terminals;
    vector <mystruct> map = gen();
    double notOpt;
    double ans = getOnly(intToArray(0), map);
    notOpt = ans;

    for (int i = 1; i < pow(2., subterm); ++i)
        ans = min(ans, getOnly(intToArray(i), map));
    return (ans - notOpt) / notOpt;
}

int main() {
    srand(1);
    for (int i = 0; i < 100; ++i)
        printf("%.2f, ", solve());
    return 0;
}