หารัศมีน้อยที่สุด ที่มีจุดอย่างน้อย k จุดอยู่ในวงกลมใน C++

สมมติว่ามีจุดบางจุด และจำนวนเต็ม k เราต้องหารัศมีน้อยที่สุดของวงกลมที่มีศูนย์กลางอยู่ที่ (0, 0) เพื่อครอบคลุม k จุด ดังนั้นถ้าจุดเป็น (1, 1), (-1, -1), (1, -1) และ k = 3 รัศมีจะเป็น 2

ที่นี่เราจะหาระยะทางยุคลิด (Euclidean Distance) ระหว่างแต่ละจุดกับ (0, 0) เรียงระยะทาง และคืนค่าองค์ประกอบลำดับที่ k หลังการเรียง

ตัวอย่าง

#include <iostream> 
#include <algorithm> 
using namespace std; 

struct point {
    int x, y;
};

int minRadius(int k, point points[], int n) {
    int dist[n];
    for (int i = 0; i < n; i++)
        dist[i] = points[i].x * points[i].x + points[i].y * points[i].y;
    // Sorting the distance
    sort(dist, dist + n);
    return dist[k - 1];
}

int main() {
    int k = 3;
    point points[] = {{1, 1}, {-1, -1}, {1, -1}};
    int n = sizeof(points) / sizeof(points[0]);
    cout << "Minimum radius: " << minRadius(k, points, n) << endl;
}

ผลลัพธ์

Minimum radius: 2