jetyb 28 июн 2018, 08:03
Задача: пусть дано n кругов на доске с радиусами r_1, ... , r_n , надо найти на доске место куда можно вписать круг с радиусом r.
Она равносильна задаче: пусть дано n кругов с радиусами r_1 + r, ... , r_n + r , надо найти на доске место куда можно поставить точку.
Наблюдение: самое компактное место для этой точки находится на границе одного из кругов r_i + r.
Алгоритм:
- для каждого существующего круга r_i проверяем его на пересечение с остальными кругами
- если он пересекается с кругом r_j, то находим точки пересечения r_i с r_j, если какая-то из них лежит вне остальных кругов (кроме r_i и r_j) и на доске, то эта точка - искомая.
- если круг r_i не пересекается ни с каим из кругов, то берем любую точку на границе r_i, лежащую на доске.
- если же на всех кругах не удалось таким действиями найти искомой точки, то точку поставить нельзя.
Сложность алгоритма O(n^3) , n - число кругов, на практике скорее O(n^2).
Можно решить и за O(n^2), если найти все точки попарного пересечения всех кругов (r_i, r_j), а затем проверить каждую из них на нахождение вне каждого круга.