假设我们有一些点和一个整数k。我们必须找到以(0,0)为中心的圆形的最小半径,以覆盖k个点。因此,如果这些点像(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; //排序距离 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