Найти пару наименее удаленных окружностей - C (СИ)

Узнай цену своей работы

Формулировка задачи:

На плоскости задано произвольно расположенных окружно- стей. Найти пару наименее удаленных из них.

Решение задачи: «Найти пару наименее удаленных окружностей»

textual
Листинг программы
#include <stdio.h>
 
typedef struct {
    int x, y, r;
} circle_t;
 
static int calc_dist(const circle_t* a, const circle_t* b){
    return ((a->x-b->x) * (a->x-b->x)  + 
            (a->y-b->y) * (a->y-b->y)) -
            (a->r+b->r) * (a->r+b->r);
}
 
//O(n^2)
static void min_dist(const circle_t* arr, size_t num, const circle_t** ca, const circle_t** cb){
    int   n, d;
    const circle_t* i, *j, *e = arr + num;
    
    if(num < 2)
        return;
 
    *ca = arr;
    *cb = arr + 1;
    d   = calc_dist(*ca, *cb);
    for(i = arr; i != e; ++i){
        for(j = i + 1; j != e; ++j){
            if((n = calc_dist(i, j)) < d){
                d   = n;
                *ca = i;
                *cb = j;
            }
        }
    }
}
 
 
int main(void){
    const circle_t *a, *b;
    circle_t arr[] = {
        {100,100,20},
        {150,160,32},
        {140,110,15},
        {110,190,10},
        {120,180, 5},
        {115,125,10}
    };
    min_dist(arr, sizeof(arr)/sizeof(arr[0]), &a, &b);
 
    printf("x: %d, y: %d, r: %d\n", a->x, a->y, a->r);
    printf("x: %d, y: %d, r: %d\n", b->x, b->y, b->r);
    return 0;
}

Объяснение кода листинга программы

В этом коде используется алгоритм для поиска двух наиболее удаленных окружностей из набора окружностей. Алгоритм работает следующим образом:

  1. Создается функция calc_dist, которая вычисляет расстояние между двумя окружностями, используя формулу расстояния между двумя точками в квадрате, вычитая сумму радиусов двух окружностей.
  2. Создается функция min_dist, которая ищет две наиболее удаленные окружности. Она проходит через все пары окружностей в наборе и вычисляет расстояние между ними. Если расстояние между текущей парой меньше, чем расстояние между текущими наиболее удаленными окружностями, то обновляются значения наиболее удаленных окружностей.
  3. В функции main создается набор окружностей и вызывается функция min_dist для поиска наиболее удаленных окружностей. Затем выводятся координаты и радиусы наиболее удаленных окружностей. Код работает правильно, если входные данные корректны (то есть набор окружностей не пустой и содержит по крайней мере две окружности). Однако, он не обрабатывает ошибки, такие как деление на ноль или выход за границы массива.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

9   голосов , оценка 3.889 из 5
Похожие ответы