C++에서 최소한 k 점이 원 내부에 있도록 최소 반지름 찾기

몇 개의 점과 하나의 정수 k가 있다고 가정합니다. k개의 점을 덮기 위해서는 중심이 (0, 0)인 원의 최소 반지름을 찾아야 합니다. 따라서 점이 (1, 1), (-1, -1), (1, -1) 및 k =3과 같으면 반경은 2가 됩니다.

여기에서 각 점과 (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