struct Solution {
    std::vector<Pnt> p;
    double currentMin;

    double recurse(int num, double dist) {

		if (dist > currentMin) {
			return currentMin + 1; //don't recurse any further if distance exceeds current minimum length.
		}

        if (num == 2) {
            return p[0].dist(p[1]) + dist; //return total length if we hit the end.
        }


        for (int i = 0; i < num - 2; ++i) {
            Pnt t1;
            t1 = p[num - 2];
            p[num-2] = p[i];
            p[i] = t1;

            for (int j = i + 1; j < num - 1; j++) {
                Pnt t2;

                t2 = p[num - 1];
                p[num-1] = p[j];
                p[j] = t2;

                double temp = recurse(num - 2, dist + p[num-2].dist(p[num-1]));

                t2 = p[num - 1];
                p[num-1] = p[j];
                p[j] = t2;

                if (temp < currentMin) {
                    currentMin = temp;
                }
            }

            t1 = p[num - 2];
            p[num-2] = p[i];
            p[i] = t1;

        }

        return currentMin;
    }

    double solve(std::vector<Pnt> input) {
        p = input;
        currentMin = std::numeric_limits<double>::max();

        return recurse(p.size(), 0.0);
    }
};