По условию получается, что в результирующем массиве может быть сколько угодно элементов - ровно столько, сколько положительных в массиве C. Вам можно использовать std::vector? Если это действительно C++, а не C, то стоит использовать его.
Andrei1penguin1, Ну запустите уже far или totalcommander, поищите в этой папке файлы с подстрокой "Py_Initialize". Найдите уже файл - библиотеку, которой не хватает и ее укажите в -l.
Andrei1penguin1, Давайте полный вывод команды (лучше на какой-нибудь pastebin, наверно). Обязательно допишите к команде "-Wl,--verbose" что бы все ошибки видеть. Еще результат dir c:/Python39/libs приведите.
Заодно, откройте либы блокнотом и поищите в них "imp__Py_Initialize"
Magneto903, Ребра просто между вершинам не нужны. Это красное ребро ни в одном оптимальном пути содержаться не будет никогда. Это легко доказать (подумайте, что будет с длиной всего пути, если один из концов отрезка чуть-чуть подвинуть в одну или другую сторону). Нужны только стороны полигонов и взаимные касательные. Ну, и отрезки между двумя внешними точками и касательные с внешних точек. Этих ребер хватит.
Magneto903, По поводу касательных - верхняя левая зеленая, рядом с красной, тоже должна быть красной. ведь она верхним концом не касается полигона.
Все касательные с одного угла правильные. Видимо, проверка, что они вторым концом касаются полигона неправильная.
В моих алгоритмах последняя точка не дублирует первую. Но допускается оборачивание вершин, и следующая за последней берется опять первая. Можно и дублировать, но тогда надо аккуратно циклы гонять что бы эта копия первой в конце не рассматривалась сама. Заодно можно и последнюю перед первой продублировать, тогда в циклах не надо будет брать индексы по модулю. Но так легко запутаться, поэтому я так не делал.
Magneto903, К сожалению, у меня нет времени досканально копаться в вашем коде. Могу лишь дать советы.
Сделайте интерактивный тестер. Создайте полигон, и стройте касательные с курсора и рисуйте их по какому-нибудь таймеру или событию перерисовки/перемещения курсора. Еще меняйте цвет полигона в зависимости от IsInside для курсора. Водите курсором по экрану, смотрите, чтоб было все правильно. Так можно проверить GetTangentsIds и IsInside. Эти функции основные и надо проверить, что они всегда работают правильно. Если будет ошибка, то захардкодьте координаты того, что на экране и пройдитесь дебаггером.
Еще проверьте, что порядок точек всегда против часовой стрелки. Многие используемые алгоритмы требуют, чтобы было именно так.
Ваша картинка указывает, что скорее всего ошибка в IsTangent и в Intersects.
Еще поможет интерактивный тестер, где можно будет таскать отрезок за его концы и рисовать разным цветом, если есть пересечение.
Это вряд ли влияет на ваши тесты, но ваш IsInside с ошибкой. Вы считаете количество пересечений луча из точки вправо. Это хороший алгоритм, но тут крайний случай, если луч проходит через вершину полигона.
Можно исправить это, изменив вашу проверку (yi > y) != (yj > y) на y > min(yi, yj) && y <= max(yi,yj). Тут важно брать один из концов (верхний или нижний) включительно, а второй пропускать. Тогда все случаи разберутся правильно.
artur_agishev, Совет на будущее, если в коде возникает такая мешанина из условий на десятки выражений, до стоит остановиться и подумать, как это упростить.
sam23q, Задание проверяет ваше понимание, а не умение нажимать ctrl-c, ctrl-v. Если вы проходите экзамен на каком-то специальном компьютере, то там почти наверняка отслеживается, что и когда вы запускаете. Там будут экзаменаторы, которые, если заметят, дадут вам по рукам или вообще выгонят с экзамена. Возможно, вы не сможете скопировать код из условия.
Я бы не надеялся, что удастся запустить код из задания. Кроме того, почти наверняка просто внимательно прочитав код и прогнав его в голове по строкам, вы решите задачу быстрее.
sam23q, В других вопросах можно строить графики/вычислять формулы в wolframalpha, гуглить теоретические вопросы. Была бы возможность не спалиться, технические способы считерить есть почти для любого вопроса.
xmoonlight, Для очень больших n, но маленьких k можно применить трюк с возведением матрицы в степень. Это будет O(k^3 log n) вместо O(kn), Но умножений BigInt-ов, а не сложений. В приведенных в задаче ограничениях это не имеет смысла.
xmoonlight, Нет, тут нет простой комбинаторной формулы. Если бы не было ограничения на размер слагаемых, то ответ был бы 2^n, Если k=2, то ответ - n-ое число фиббоначи. Для произвольного k тут некое обобщение чисел фиббоначи. Простой и замкнутой формулы тут нет. Можно, конечно, иррациональные корни характеристического многочлена возводить в степень, как золотое сечение для чисел фиббоначи, но это применимо только для маленьких k, да и это решение будет гораздо сложнее при реализации, ведь тут нужна точность в сотни знаков. Это значит, надо вместо сложения BigInt-ов реализовывать произведения, деления, корни для чисел с фиксированной точкой.
Дима Щеглов, Я об этом и написал в самом конце моего ответа. Но надо еще присвоение в начале исправить. Иначе алгоритм может упасть с выходом за границу массива.
