ধরুন আমাদের একটি পয়েন্ট সেট আছে। আমাদের কাজ হলো উদ্ভূত বিন্দু (0,0) থেকে K সংখ্যক নিকটতম পয়েন্ট বের করা। ধরুন পয়েন্টগুলো হলো (3, 3), (5, -1) এবং (-2, 4)। তখন K = 2 হলে নিকটতম দুটি পয়েন্ট হবে (3, 3) এবং (-2, 4)।
এই সমস্যাটি সমাধান করতে পয়েন্ট লিস্টকে তাদের ইউক্লিডিয়ান দূরত্ব অনুযায়ী সর্ট করতে হবে, তারপর সর্ট করা লিস্ট থেকে শীর্ষের Kটি উপাদান নিতে হবে। সেগুলোই Kটি নিকটতম পয়েন্ট।
উদাহরণ
#include<iostream> #include<algorithm> using namespace std; class Point{ private: int x, y; public: Point(int x = 0, int y = 0){ this->x = x; this->y = y; } void display(){ cout << "("<<x<<", "<<y<<")"; } friend bool comparePoints(Point &p1, Point &p2); }; bool comparePoints(Point &p1, Point &p2){ float dist1 = (p1.x * p1.x) + (p1.y * p1.y); float dist2 = (p2.x * p2.x) + (p2.y * p2.y); return dist1 < dist2; } void closestKPoints(Point points[], int n, int k){ sort(points, points+n, comparePoints); for(int i = 0; i<k; i++){ points[i].display(); cout << endl; } } int main() { Point points[] = {{3, 3},{5, -1},{-2, 4}}; int n = sizeof(points)/sizeof(points[0]); int k = 2; closestKPoints(points, n, k); }আউটপুট
(3, 3) (-2, 4)
