Привет, сейчас прохожу курс от RuCode на Степике по введению в спортивное программирование и застрял на задаче из темы "Бинарный поиск". Задача состоит в том чтобы с помощью бинарного поиска найти точку пересечения окружности и кривой, заданной многочленом степени не выше 4.
Формулировка: Дана окружность, многочлен и точка X. Гарантируется, что (x, f(x)) лежит внутри окружности. Найти пересечение многочлена с окружностью.
Понятно что если у нас есть точка лежащая внутри окружности, то мы можем использовать ее как левую границу бинарного поиска, но непонятно по какой функции производить этот бинарный поиск и как искать правую границу. Буду благодарен за любую помощь!
Вы знаете центр окружность и ее радиус. Какая самая правая точка на окружности?
Понял, а как быть с функцией по которой нужно строить бинпоиск?
Интересующая функция возвращает true, если точка $$$(x, f(x))$$$ лежит внутри окружности, а в противном случае возвращает false. Вам нужно найти границу true и false.
Не совсем понятно как это выразить математически, можете подробнее расписать, пожалуйста?
В это трудно поверить, но точка лежит внутри окружности, если расстояние от центра окружности до этой точки меньше радиуса окружности.