सी ++ में दिए गए बिंदुओं के सेट के लिए सरल बंद पथ खोजें

विचार करें कि हमारे पास बिंदुओं का एक सेट है। हमें सभी बिंदुओं को कवर करते हुए एक सरल बंद रास्ता खोजना होगा। मान लीजिए कि बिंदु नीचे की तरह हैं, और अगली छवि उन बिंदुओं पर एक बंद पथ बना रही है।

रास्ता पाने के लिए हमें इन चरणों का पालन करना होगा -

• नीचे बाएँ बिंदु को P के रूप में खोजें

• अन्य n - 1 बिंदु को P के चारों ओर वामावर्त ध्रुवीय कोण के आधार पर क्रमबद्ध करें, यदि दो बिंदुओं के ध्रुवीय कोण समान हैं, तो उन्हें सबसे कम दूरी के रूप में रखें

• अंक की क्रमबद्ध सूची को पार करें, फिर पथ बनाएं

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Point {
   public:
   int x, y;
};
Point p0;
int euclid_dist(Point p1, Point p2) {
   return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}
int orientation(Point p1, Point p2, Point p3) {
   int val = (p2.y - p1.y) * (p3.x - p2.x) - (p2.x - p1.x) * (p3.y - p2.y);
   if (val == 0) return 0; // colinear
   return (val > 0)? 1: 2; // clockwise or counterclock wise
}
int compare(const void *vp1, const void *vp2) {
   Point *p1 = (Point *)vp1;
   Point *p2 = (Point *)vp2;
   int o = orientation(p0, *p1, *p2);
   if (o == 0)
   return (euclid_dist(p0, *p2) >= euclid_dist(p0, *p1))? -1 : 1;
   return (o == 2)? -1: 1;
}
void findClosedPath(Point points[], int n) {
   int y_min = points[0].y, min = 0;
   for (int i = 1; i < n; i++) {
      int y = points[i].y;
      if ((y < y_min) || (y_min == y && points[i].x < points[min].x))
      y_min = points[i].y, min = i;
   }
   swap(points[0], points[min]);
   p0 = points[0];
   qsort(&points[1], n-1, sizeof(Point), compare); //sort on polar angle
   for (int i=0; i<n; i++)
   cout << "(" << points[i].x << ", "<< points[i].y <<"), ";
}
int main() {
   Point points[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},{0, 0}, {1, 2}, {3, 1}, {3, 3}};
   int n = sizeof(points)/sizeof(points[0]);
   findClosedPath(points, n);
}

आउटपुट

(0, 0), (3, 1), (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (0, 3),