หา K Closest Points ไปยัง Origin ใน C++

สมมติเรามีชุด Points ต้องการหา K Points ที่อยู่ใกล้ Origin มากที่สุด สมมติ Points คือ (3, 3), (5, -1) และ (-2, 4) แล้ว K = 2 จุดที่ใกล้ที่สุดคือ (3, 3) และ (-2, 4)

วิธีแก้: เรียง Points ตาม Euclidean Distance จาก Origin แล้วเอา K จุดแรกจากรายการที่เรียงแล้ว

ตัวอย่างโค้ด C++

#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)