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

	double recurse(int num, double dist) {

		if (num == 2) {
			return p[0].dist(p[1]) + dist;
		}


		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);
	}
};