Я бы искал точку для которой максимально расстояние до ближайшего бота. Это делается одной дейкстрой - добавьте в граф новую вершину и ребра длины 0 во всех красных ботов. Потом ищите самую далекую точку от этой новой.
По ботам я бы убегал от самого близкого. Или, опять же, брал всех ботов с коэффициентами обратнопропорциональными квадрату расстояния. Тогда будет сильнее убегать от ближайшего, но и остальные будут немного влиять на решения.
Нет-нет, расстояние не тупо по плоскости а по ребрам графа. Поэтому вам нужно запустить одну дейкстру от красного бота, найти самую далекую вершину, и запустить вторую дейкстру из нее.
Посмотрите на все соседние вершины от зеленого бота. Одни из них ближе к самой далекой вершине и ведут к ней, другие - дальше. Можно ввести что-то типа косинуса - отношение изменения расстояния до самой далекой точки и длины ребра. Так, ребро, лежащее на пути в эту наиудаленнейшую точку будет давать 1. Ребра, ведущие от этой точки будут давать -1. Аналогично можно найти эту метрику относительно вершины в которой красный бот. Это косинус вашего синего угола на графике (-1 для идти от красного бота и +1 для идти на него), если есть прямая видимость.
Надо эти 2 метрики как-то смешать с коэффициентами и брать самое хорошее значение жадно. Коэффициенты берите такого знака, чтобы поощрять движение к самой далекой точке и от красного бота. Кажется, движение от красного бота должно идти с большим коэффициентом. Можно их делать нелинейными - если идем к красному боту, то штраф с большим коэффициентом, чем бонус от ходьбы от бота.
Можно сделать бота ходящего не по вершинам графа. Вот вы нашли путь от красного бота до зеленого и у вас есть входящий вектор - последнее ребро. Еще вы нашли путь от самой дальней точки (для красного бота) до этого же зеленого бота. Опять, есть входящий вектор по последнему ребру - разверните его. Теперь у вас есть 2 вектора - один от красного бота, другой - в самую далекую точку. И вам надо как-то между этими векторами выбирать. Например, складывайте их с разными коэффициентами - вот и будет ваше направление для зеленого бота.
Magneto903, Найдите расстояния от преследователя до всех вершин. Найдите самую далекую вершину. Найдите расстояния от этой вершины до всех остальных. Выбирайте то ребро, которое уводит от преследователя и при этом уменьшает расстояние до самой далекой вершины.
В этом случае зеленый будет локально не идти на встречу красному и не будет заходить в тупик, потому что этот тупик удлиняет расстояние до самой далекой вершины.
Это будет работать плохо только если зеленый уже в тупике и прижат красным.
По условию получается, что в результирующем массиве может быть сколько угодно элементов - ровно столько, сколько положительных в массиве 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-ов реализовывать произведения, деления, корни для чисел с фиксированной точкой.
По ботам я бы убегал от самого близкого. Или, опять же, брал всех ботов с коэффициентами обратнопропорциональными квадрату расстояния. Тогда будет сильнее убегать от ближайшего, но и остальные будут немного влиять на решения.