На плоскости даны n точек с координатами. Необходимо накрыть по крайней мере k из них кругом с центром на оси Ox. Найдите наименьший возможный радиус такого круга с точностью до 10^-3.
Решение нужно на С++ со сложностью не более О(n^2).
Знаю про алгоритм Вельцля. Также пыталась гуглить. Все найденные алгоритмы не учитывают, что центр круга должен лежать на оси Ох. Как их переделать под свою задачу - уже сломала голову.
Функция, которую мне предложил ChatGPT (передаются точки и количество точек, которое надо покрыть), но также не учитывает центр на оси Ох.
double getDistance(const pair<int, int>& p1, const pair<int, int>& p2) {
double dx = p1.first - p2.first;
double dy = p1.second - p2.second;
return sqrt(dx * dx + dy * dy);
}
pair<double, pair<int, int>> getMinimalCircle(const vector<pair<int, int>>& points, int numPoints) {
vector<pair<int, int>> selectedPoints(points.begin(), points.begin() + numPoints);
random_shuffle(selectedPoints.begin(), selectedPoints.end());
pair<int, int> center = selectedPoints[0];
double radius = 0.0;
for (int i = 1; i < numPoints; i++) {
if (getDistance(center, selectedPoints[i]) > radius) {
center = selectedPoints[i];
radius = 0.0;
for (int j = 0; j < i; j++) {
if (getDistance(center, selectedPoints[j]) > radius) {
center.first = (selectedPoints[i].first + selectedPoints[j].first) / 2;
center.second = 0;
radius = getDistance(center, selectedPoints[j]);
for (int k = 0; k < j; k++) {
if (getDistance(center, selectedPoints[k]) > radius) {
center.first = ((selectedPoints[i].first + selectedPoints[j].first) / 2 + selectedPoints[k].first) / 2;
center.second = 0;
radius = getDistance(center, selectedPoints[k]);
}
}
}
}
}
}
return make_pair(radius, center);
}