Найти пару наименее удаленных окружностей - 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; }
Объяснение кода листинга программы
В этом коде используется алгоритм для поиска двух наиболее удаленных окружностей из набора окружностей. Алгоритм работает следующим образом:
- Создается функция
calc_dist
, которая вычисляет расстояние между двумя окружностями, используя формулу расстояния между двумя точками в квадрате, вычитая сумму радиусов двух окружностей. - Создается функция
min_dist
, которая ищет две наиболее удаленные окружности. Она проходит через все пары окружностей в наборе и вычисляет расстояние между ними. Если расстояние между текущей парой меньше, чем расстояние между текущими наиболее удаленными окружностями, то обновляются значения наиболее удаленных окружностей. - В функции
main
создается набор окружностей и вызывается функцияmin_dist
для поиска наиболее удаленных окружностей. Затем выводятся координаты и радиусы наиболее удаленных окружностей. Код работает правильно, если входные данные корректны (то есть набор окружностей не пустой и содержит по крайней мере две окружности). Однако, он не обрабатывает ошибки, такие как деление на ноль или выход за границы массива.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д