0

На плоскости даны 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);
}
2
  • Скажите - а если вам дан радиус круга, вы можете за O(n) посчитать максимальное количество точек, которое он может накрыть, если центр где-то на OX?
    – MBo
    Commented 12 окт. 2023 в 15:45
  • вы знаете линейный алгоритм для описанной мной подзадачи или предполагаете, что он есть? Я пока только предполагаю. И ещё вопрос - каков диапазон координат?
    – MBo
    Commented 12 окт. 2023 в 16:17

1 ответ 1

0

Если дан радиус круга R, то для каждой точки мы можем посчитать, в каком диапазоне позиций центра круга по X она будет лежать в круге. Таким образом, образуется не более N интервалов (часть точек за полосой полуширины R никогда не попадут в круг и не образуют интервалов). Мы можем отсортировать их концы за O(NlogN) и найти отрезок по оси OX, при расположении центра круга в котором круг данного радиуса покроет наибольшее количество точек. Для нас важно только это количество точек.

Понятно, что зависимость количества точек от радиуса монотонная - значит, мы можем применить метод бинарного поиска по радиусу, пока не достигнем нужной точности в 0.001, обеспечив k точек в круге.

Сложность получается O(NlogN*log(CoordinateRange))

Если первую задачу можно решить за линейное время, то ещё лучше получится.


Расшифровка подзадачи с интервалами:

Точка (x,y), если abs(y)<=R, может входить в круги с центром в диапазоне

X0=x-sqrt(R^2-y^2)...X1=x+sqrt(R^2-y^2)

Добавляем в вектор или список пару <X0, 1> и пару <X1, -1>.

Обработав все точки, сортируем список по первому элементу, при равенстве учитываем второй элемент.

Ставим счётчик в 0, идём по списку, на каждом шаге добавляя к счётчику второй элемент пары. Максимальное значение счётчика - максимальное количество покрытых точек. Само значение координаты роли не играет, но в принципе отрезок доступен.


Бинарный поиск по ответу:

lo = 0;
hi = 2000;
while (hi - lo > 0.0001) {
    m = (lo + hi) / 2;
    cnt = points_in_circle(m); //это функция с кодом, описанным выше
    if (cnt < k)
        lo = m;
    else
        hi = m;
}
return lo;  //искомый радиус
10
  • Вы понимаете, как работает бинарный поиск по решению? Берем R = R0 (максимальной разнице координат), считаем, сколько максимум точек может содержать такой круг. Если больше k - делим радиус пополам, опять считаем макс. количество точек для R0/2. Если больше k - переходим к R0/4 и продолжаем, если меньше - переходим к 3/4*R0 и продолжаем. Так до тех пор, пока шаг не станет меньше 0.001
    – MBo
    Commented 12 окт. 2023 в 16:46
  • Добавил описание.
    – MBo
    Commented 12 окт. 2023 в 17:04
  • В вашем примере минимальный радиус - корень из двух, не единица. Commented 12 окт. 2023 в 22:06
  • 1
    Вы молодец, что все реализовали, это не так уж просто. Вероятно, неверно выбран R0. Ещё момент - нужна разновидность бинарного поиска leftmost
    – MBo
    Commented 13 окт. 2023 в 1:24
  • Начальное значение R0 как установили?
    – MBo
    Commented 13 окт. 2023 в 9:25

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.