Спасите Землю

Рассмотрим кратчайшие отрезки от точки до одного круга и до другого. Если отрезок задевает оба круга, обновим ответ.

Теперь посмотрим, как выглядит решение. Сначала из точки нужно провести отрезок до какой-то точки на одной окружности, потом из этой точки провести отрезок до точки на второй окружности по направлению к центру этой окружности. Второй отрезок надо проводит в направлении центра второй окружности, потому что требуется из какой-то точки за минимальное расстояние дойти до окружности. Заметим, что ответом будет |a - p| + |c - p| - rc, где a — начальная точка, p — точка на первой окружности, c — центр второй окружности, rc — ее радиус. Следовательно, нужно минимизировать |a - p| + |c - p|, потому что rc — константа.

Рассмотрим порядок, в котором будут посещены окружности. Найдем минимум требуемой функции. Это можно сделать с помощью тернарного поиска по углу точки p из b, где b — центр первой окружности, выбрав в качестве границ тернарного поиска углы точек a и c из b.