Advertisement
Guest User

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. };
Advertisement
RAW Paste Data Copied
Advertisement