Застывший Мир

Автор задачи: Даниил Голов, разработчик: Константин Бац

Суть задачи заключалось в том, чтобы найти центр некоторого круга неизвестного радиуса $$$2d$$$. Для этого у нас есть единственная операция: проверить, лежит ли некоторая точка $$$(x, y)$$$ внутри искомого круга или нет.

Задачу можно решить, если найти три точки, лежащие на границе круга с центром в искомой точке. Проведем из точки $$$(0, 0)$$$ три луча в разных направлениях, которые пересекутся с границей круга. При этом, условие, что точка $$$(0, 0)$$$ находится на расстоянии не больше $$$d$$$ от $$$(x, y)$$$, гарантирует нам, что точки пересечения с границей круга будут различными.

Выбор направления лучей не имел значения. Например, можно было взять направления $$$(-1, 0)$$$, $$$(0, 1)$$$ и $$$(0, 1)$$$. Далее нужно найти точку пересечения каждого из лучей с границей круга. Для этого будем искать максимальное удаление от точки $$$(0, 0)$$$ в направлении луча, при котором она все еще находится на расстоянии не больше $$$2d$$$ от центра круга. По условию задачи, такое удаление нужно искать на отрезке $$$[0, 10^6]$$$, а достаточная точность при бинарном поиске — $$$10^{-3}$$$ (если взять направления, параллельные осям координат).

Таким образом, для решения достаточно запустить три бинарных поиска в различных направлениях, а затем найти центр круга по трем точкам. Пусть $$$(x_1, y_1)$$$, $$$(x_1, y_1)$$$, $$$(x_1, y_1)$$$ — найденные точки на окружности, а $$$(x, y)$$$ — центр круга. Тогда, если обозначить $$$m_1 = \frac{y_2 - y_1}{x_2 - x_1}$$$, и $$$m_2 = \frac{y_3 - y_2}{x_3 - x_2}$$$, то можно построить следующую систему уравнений $$$$$$ \begin{cases} y = - \frac{1}{m_1}\cdot\left(x - \frac{x_1 + x_2}{2}\right) + \frac{y_1 + y_2}{2} \\ y = - \frac{1}{m_2}\cdot\left(x - \frac{x_2 + x_3}{2}\right) + \frac{y_2 + y_3}{2} \\ \end{cases} $$$$$$

Для решения системы уравнений выразим $$$x$$$ следующим образом, а затем с его помощью найдем $$$y$$$. $$$$$$ x = \frac{ m1 \cdot m2 \cdot (y_1 - y_3) + m2 \cdot (x_1 + x_2) - m1 \cdot(x_2 + x_3) }{2 \cdot (m2 - m1)} \text{.} $$$$$$