# Untitled

a guest
Jan 11th, 2020
120
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct Solution {
2. std::vector<Pnt> p;
3. double currentMin;
4.
5. double recurse(int num, double dist) {
6.
7. if (dist > currentMin) {
8. return currentMin + 1; //don't recurse any further if distance exceeds current minimum length.
9. }
10.
11. if (num == 2) {
12. return p[0].dist(p[1]) + dist; //return total length if we hit the end.
13. }
14.
15.
16. for (int i = 0; i < num - 2; ++i) {
17. Pnt t1;
18. t1 = p[num - 2];
19. p[num-2] = p[i];
20. p[i] = t1;
21.
22. for (int j = i + 1; j < num - 1; j++) {
23. Pnt t2;
24.
25. t2 = p[num - 1];
26. p[num-1] = p[j];
27. p[j] = t2;
28.
29. double temp = recurse(num - 2, dist + p[num-2].dist(p[num-1]));
30.
31. t2 = p[num - 1];
32. p[num-1] = p[j];
33. p[j] = t2;
34.
35. if (temp < currentMin) {
36. currentMin = temp;
37. }
38. }
39.
40. t1 = p[num - 2];
41. p[num-2] = p[i];
42. p[i] = t1;
43.
44. }
45.
46. return currentMin;
47. }
48.
49. double solve(std::vector<Pnt> input) {
50. p = input;
51. currentMin = std::numeric_limits<double>::max();
52.
53. return recurse(p.size(), 0.0);
54. }
55. };