সমস্যা বিবরণ
একই সেট পয়েন্ট দিয়ে কনভেক্স হাল বের করতে হবে জারভিস অ্যালগরিদম (Jarvis's Algorithm) ব্যবহার করে। কনভেক্স হাল হলো সবচেয়ে ছোট কনভেক্স পলিগন যা সব পয়েন্ট বাউন্ডারি বা ভিতরে ধারণ করে।
জারভিস অ্যালগরিদমে সবচেয়ে বামের পয়েন্ট বেছে নেওয়া হয় এবং ক্লকওয়াইজ দিয়ে পয়েন্ট র্যাপ করা হয়।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
};
int cal_orientation(Point p, Point q, Point r) {
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // collinear
return (val > 0) ? 1 : 2; // clock or counterclockwise
}
void convexHull(Point points[], int n) {
if (n < 3) return;
vector<Point> hull;
int l = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[l].x) l = i;
int p = l, q;
do {
hull.push_back(points[p]);
q = (p + 1) % n;
for (int i = 0; i < n; i++) {
if (cal_orientation(points[p], points[i], points[q]) == 2)
q = i;
}
p = q;
} while (p != l);
for (int i = 0; i < hull.size(); i++)
cout << "(" << hull[i].x << ", " << hull[i].y << ")\n";
}
int main() {
Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1}, {3, 0}, {0, 0}, {3, 3}};
int n = sizeof(points)/sizeof(points[0]);
convexHull(points, n);
return 0;
}
আউটপুট
(0, 3) (0, 0) (3, 0) (3, 3)
