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

Giả sử chúng ta có một số điểm và một số nguyên k. Ta phải tìm bán kính nhỏ nhất của đường tròn có tâm tại (0, 0) để bao phủ k điểm. Vì vậy, nếu các điểm giống như (1, 1), (-1, -1), (1, -1) và k =3, thì bán kính sẽ là 2.

Ở đây chúng ta sẽ tìm khoảng cách Euclid giữa mỗi điểm và (0, 0), sau đó sắp xếp các khoảng cách và trả về phần tử thứ k sau khi sắp xếp.

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

Đầu ra

Minimum radius: 2