В смысле - не верной? Она верная. Такая полиномиальная кривая обязательно на бесконечности x уйдет в бесконечность по y. Полиномы Лагранжа лишь гарантируют, что кривая пройдет через ключевые точки. А дальше она может идти как угодно.
Если вам надо, чтобы ваша кривая была более менее пологая везде, то полиномиальная интерполяция вам не подходит. Или надо смотреть на кривую только от первой до последней точки. За ними продолжать кривую нельзя.
EvgenyApMr, Тогда почему вы работаете только с x до 100, если точка, через которую кривая должна пройти, имеет координату 106?
И вообще, циклы у вас странные. Почему-то от 0, хотя в паскале (это же паскаль?) индексация вроде как с 1 была. Судя по графику, похоже, что последняя точка тупо не учитывается у вас почему-то. А в остальном все правильно - кривая проходит через нужные точки.
EvgenyApMr, Нет. Все разности в p остаются xArray. Но потом надо будет p домножить на yarray[i]. И вот это вот прибавить к yt. Внутри цикла по i. А вот xt вычисляется в цикле по a.
Подумайте сами, вот эта вот формула (t-t[j])(t[i]-t[j]) дает 1 при t=t[i] и 0 для t равных другим индексам. Значит, если ее брать в качестве множителя перед значением точки i, то при x равном xarray[i], именно эта точка возьмется с множителем 1, а все остальные возьмутся с множителем 0.
Т.е. Цикл по a (он же по x), цикл по i, внутри считаем формулу лагранжа для всех j != i. После цикла по j это домножаем на y[i] и суммируем.
EvgenyApMr,
Тогда вам надо xt делать a. При вычислении p надо домножать на yArray[i], а не x. Все p в цикле по i надо будет просуммировать - это и будет значение yt.
max_haker, между двумя точками существует бесконечно много углов. Угол описывается вершиной и двумя лучами. Ну, или тремя точками (вершина и две точки). Что за две точки у вас заданы? Отметьте их на картинке.
rPman, куки? Я в файерфоксе никаких паролей не ввожу, а сайты все меня помнят. То же и с хромом. Вылогинивание из гуглового аккаунта не стирает куки сайтов. Может быть, сохраненные пароли еще и зашифрованы как-то, но по-моему и этого нет.
KeksikProg, Советую при компиляции включить все предупреждения. Тогда вам компилятор про эту ошибку бы несколько раз ругнулся. При вызове у вас преобразование char* в char, с потерей данных. В самой функции наоборот.
mayton2019, Так-то и свап с аргументами-ссылками может быть лямбдой. Правда, зачем кому-то может понадобится лямбда, меняющая местами 2 аргумента, я не могу представить. Особенно, лямбда, которая возвращает аргументы в паре. Этакий make_pair, но переставляющий элементы.
mayton2019, Можно. Но это не помена значений на месте. Чтобы поменять значения, надо будет еще эту пару назад присвоить, и это будет 2 временные пересенные (в паре), вместо одной.
alex_l2005, Ну вообще оно будет чуть быстрее O(n^2.5) вместо O(n^3). Но поможет ли это - неясно. Может, тут можно 2 бинпоиска в один объединить. Дальше идут какие-то идеи, но более быстрого решения я пока не придумал.
Вот перебрали вы время в ответе. Построили окружности - куда можно с каждой точки дойти за это время.
Каждая такая окружность пересекает окружность R по отрезку. Построили вы n таких отрезков. Также разбейте окружность на n интервалов, в каждом из которых должна быть вершина многоугольника.
Если какой-то 1/n интервал целиком покрыт окружностью из изначальной точки, то вот этот жук вот до этой вершины мноугольника доедет с любым углом. Если же отрезок покрыт не целиком, то взяв это ребро, вы наложите ограничение на угол - он должен быть в пересечении отрезка пересечения окружностей и 1/n дуги. Может, сдвинув все отрезки в одну дугу 1/n окружности, попересекая все со всем, вы найдете O(n) возможных углов, в каждом из которых есть только какие-то дуги.
Вообще, можно подумать, а в каком случае что-то в ответе меняется. Если чуть чуть поуменьшать/поувеличивать время в ответе, то пересечения с окружностью радиуса R тоже чуть-чуть сожмуться, разожмутся. И что-то принципиально поменяется только когда 2 отрезка на окружности станут пересекаться, или какой-то отрезок зайдет на нувую 1/n дуги.
Соответственно, вы можете найти все O(n*n) интересных расстояний, потом обработать из все в порядке увеличения. И там, каждый раз добавляются какие-то ребра в двудольный граф. Ну надо поискать, а нет ли удлиняющей цепи вот через эти, добавляемые ребра.
Если вам надо, чтобы ваша кривая была более менее пологая везде, то полиномиальная интерполяция вам не подходит. Или надо смотреть на кривую только от первой до последней точки. За ними продолжать кривую нельзя.