สมมุติว่าเรามีจุด, และจำนวนเต็ม k หนึ่งตัว เราต้องหารัศมีต่ำสุดของวงกลมที่มีจุดศูนย์กลางอยู่ที่ (0, 0) เพื่อให้ครอบคลุมจุด k ดังนั้นหากจุดเช่น (1, 1), (-1, -1), (1, -1) และ k =3 แล้วรัศมีจะเป็น 2
ที่นี่ เราจะพบระยะทางแบบยุคลิดระหว่างแต่ละจุดกับ (0, 0) จากนั้นจัดเรียงระยะทางและส่งคืนองค์ประกอบ kth หลังจากจัดเรียง
ตัวอย่าง
#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
