Tìm bán kính nhỏ nhất để ít nhất k điểm nằm trong đường tròn trong C++

Cho các điểm và k, tìm bán kính nhỏ nhất của đường tròn tâm (0,0) bao phủ ít nhất k điểm. Ví dụ điểm (1,1), (-1,-1), (1,-1), k=3 → bán kính 2.

Tính khoảng cách Euclid bình phương từ mỗi điểm đến gốc, sắp xếp, lấy phần tử thứ k.

Ví dụ

#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; }

Kết quả

Minimum radius: 2