Дистанционная подготовка: Задача "Две окружности" с региона
Задача "Две окружности" с региона
от Георгий Корепанов - Суббота 25 Январь 2014, 22:29
111494. Две окружности
  Натолкните, если можно, на мысль. Написал функции вычисления центра окружности по трем точкам. Перебирать все варианты - сложность O(n^3), как минимум. Нужна какая-то оригинальная идея отбора точек - ничего не могу придумать. Заранее спасибо)
Re: Задача "Две окружности" с региона
от Peter Cherepanov - Воскресенье 26 Январь 2014, 10:24
  Окружность может пересекать 2 другие окружности в 4 точках. Значит, через 4 точки может проходить ложная окружность, но 5 точек всегда принадлежат правильной окружности.

Возьмите любые 9 точек. 5 из них принадлежат одной из окружностей. Найдите такую окружность полным перебором.

Разберите все точки по принадлежности к первой или второй окружности. Не забывайте про особые случаи.

Случаи с малым числом точек нужно обрабатывать отдельно.
Re: Задача "Две окружности" с региона
от Георгий Корепанов - Воскресенье 26 Январь 2014, 12:58
  Спасибо большое, именно так сейчас и решил, правда, с граничными случаями не разобрался, позже разберусь.