Wataru

Логика у вас правильная - взять середину отрезка AB и отложить от него перпендикуляр длинной sqrt(3)/2*d.

Но не надо искать углы, вектор перпендикуляр находится тривиально - это {y2-y1, x1-x2} (Можно доказать перпендикулярность через скалярное произведение, например). Более того, длина этого вектора будет уже d (это ведь повернутый на 90 градусов вектор по стороне треугольника). Значит его остается тупо домножить на sqrt(3)/2.

Таким образом формула x3 = (x1+x2)/2 +sqrt(3)/2*(y2-y1).

Во-первых, берите две соседние стороны многоугольника. Если они коллинеарны, то берите другие 2 соседние. Но по хорошему, у вас коллинеарных соседних строн быть не должно и их можно объеденить при вводе полигона.

Но все-равно остается вопрос, а вдруг нормаль смотрит в сторону отчки (0,0,0).
Постройте уравнение плоскости ax+by+cz+d=0. (a,b,c) - это ваш найденный вектор нормали. d высчитывается, если подставить одну любую точку полигона.

Теперь, если d положительно, то точка (0,0,0) лежит в том полупространстве, куда смотрит вектор и вам надо развернуть нормаль.

Тут используется свойство знакового расстояния. Можно в уравнение плоскости подставить любую точку. Вы получите 0 для плоскости, положительные числа для одного полупространства и отрицательные для другого. Положительные в той части, куда торчит вектор нормали (ведь если отложить от точки на плоскости эту нормаль, и подсчитать знаковое расстояние, то получите тупо длину вектора нормали).

Это не совсем ним (где несколько кучек и за ход можно взять сколько угодно камней). Судя по коду, игроки могут брать 1,2 или 3 камня и кучка одна. Кажется, у вас выигрывает тот, кто возьмет последний камень.

Сначала немного теории игр.
Если камней 1-3, то первый игрок выигрывает (очевидно, беря все). Если камней 4, то любой ход приведет к выигрышной позиции. Значит 4 - это проигрышная позиция. Начинающий в ней ВСЕГДА проигрывает (если второй игрок, конечно, не поддается и не делает глупостей). Далее чуть чуть логики и становится понятно, что любая позиция вида 4*k проигрышная. Выигрышный ход - вычесть n%4 камня, чтобы врагу досталась пощиция с делящимся на 4 количеством камней. Что вы делаете из такой проигрышной позиции неважно.

Поэтому для 8 камней, если начинает бот, и человек действует правильно - бот всегда проиграет.

Правильная функция choize должна быть:

def choose(s):
  if s%4 == 0: return 1
  else return s%4

Тогда бот обязательно выиграет, если выигрышная позиция есть, или если человек допустит ошибку, хоть у него и была выигрышная стратегия.

Еще по коду. Вместо if i==0 else if i ==1, можно просто делать i=1-i. а лучше вместо i=0 заведите bots_move = true и делайте bots_move = not bots_move.
Вместо s назовите переменную num_stones. Вместо a - human_move. Некоторые ваши комментарии в коде бесполезны, ибо они просто дублируют код, а не объясняют зачем или почему этот код таков.

Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

Теперь можно считать ботов точками и они могут касаться полигонов.

Постройте граф. Вершины в графе - вершины полигонов, боты и игрок. Для каждой вершины и другого полигона найдите 2 касательные с точки на полигон - можно перебрать все отрезки из вершины на другой полигон и отбросить те, относительно которых 2 стороны второго многоугольника лежат по разные стороны. Также все эти касательные проверьте на пересечение со всеми остальными полигонами и удалите те, которые пересекаются (проверьте каждую сторону полигона, и пересеките сторону с известным отрезком-касательной).

Теперь у вас остались только касательные, по которым имеет смысл ходить. Добвьте их в граф (длины ребер равны длине отрезков).
Также добавьте в граф все ребра многоугольников. Все кратчайшие пути мужду всеми точкаим идут в этом графе. Вы или идете вдоль полигона, или идете из текущей точки по касательной к какому-то полигону. Очевидно, что это любой другой путь можно улучшать, пока он не станет состоять из этих кусков.

Теперь, для каждого бота и игрока сделайте то же самое - постройте касательные на все многоугольники, удалите те, которые пересекаются с другими полигонами. Также добавтье прямые пути игрок-бот, если нет пересечений с полигонами. В этом графе нужно найти кратчайшие пути (лучше Дейкстрой от игрока до всех ботов).

Обход других ботов делается так - у ботов есть подсчитанные пути. Боты пытаются сделать маленькие шаги вдоль пути. Если они пересекаются с другим ботом, то можно пропустить ход, или попытаться толкнуть другого бота. Расствьте ботам случайные приоритеты и, если бот с большим приоритетом хочет пересечься с ботом с меньшим приоритетом, то второй делает шаг назад.

Они будут толпиться в узких проходах, но в итоге выстроятся шеренгой и пойдут друг за другом. Но это если игрок один. Тогда боты идут в одну сторону. Если они могут ходить против друг друга, то будет хуже. Они могут запереть друг друга в узком проходе и долго выталкивать друг друга.

Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.

Я придумал решение через динамическое программирование.

Предположение - цены у каждого поставщика не возрастают при увеличении количества заказов. В противном случае, это бред какой-то, а не поставщики.

Ключевое наблюдение - если есть какой-то ответ (распределение заказов по поставщикам), то среди всех активных поставщиков всегда есть кто-то один, у которого текущая цена минимальна. Можно скидывать ему товары от остальных, пока не упремся в границу переключения цены у них. При этом цена у этого поставщика может еще и улучшиться. Общая сумма только улучшиться от этого. Если упремся в запасы этого поставщика, то можно его исключить из рассмотрения и повторить операцию. Таким образом, лишь улучшая ответ, мы придем к тому, что какие-то поставщики продают весь свой запас целиком, какой-то один продает сколько-то (и его цена меньше всех оставщихся). Все оставшиеся продают ровно минимальное количество для какой-то цены (ключ из входных данных). Можно в массив цен у каждого поставщика дописать вариант => <последняя цена>, если там такой записи еще нет. И еще запишите туда 0 => 0 в начало (купить 0 за 0). Тогда все еще упрощается - все поставщики, кроме одного, продают ровно какой-то свой priceBreak штук.

Это простое рассуждение говорит нам, что искать оптимальный ответ можно только среди вот этих вот описанных выше. Потому что любой вариант можно свести к такому, возможно даже улучшив его.

Это уже можно свести к чему-то вроде задачи о рюкзаке. Переберите одного особого поставщика (который будет продавать не фиксированное количество штук). Исключите его из массива поставщиков (но запомните его цены, чтобы считать, сколько ему придется заплатить за остаток).

Теперь, как в задаче о рюкзаке, считайте динамическое програмимрование DP(i,j) - какая минимальная цена, чтобы набрать ровно i штук у первых j заказчиков (и каждый продает ровно какой-то свой priceBreak).

База тривиальна: DP(0,0) = 0, DP(i>0, 0) = infinity (на практике - большое число, или -1 и это значение надо отдельно проверять при переходе).

Переход:

DP(i,j) = min_{k : priceBreak[j][k]<=i} DP(i-priceBreak[j][k], j-1) + priceBreak[j][k]*cost[j][k]

Тут мы просто перебираем, сколько продает последний поставщик. Берем оставшиеся у предыдущих (DP(...,j-1) и прибавляем, сколько заплатим последнему.

Вот, подсчитали вы ДП. Теперь ответ - min_{i <= n, i <= stock} DP(n-i,m) + (i)*cost(i). Перебирайте, сколько вы купите у особого поставщика. Берите оставшееся из динамического программирования.

Если поставщиков M, надо купть N штук, у каждого поставщика по K цен, но это решение будет O(M*(M*N*K + N)) по времени и O(M*N) по памяти. (На самом деле, можно уточнить оценку по времени- O(M*(M*N+N*L+N)), где L - общее количество записей в массивах цен у всех поставщиков).

Для восстановления ответа вместе с DP() запоминайте, какое значение k выдало лучший результат. Потом можно будет с конца размотать оптимальный ответ, выдавая известное значение последнему поставщику.

Если цены у поставщиков могут возрастать при увеличении количества, то решение остается в силе, только надо дописать в каждый массив "количество=>цена" элементы с количеством на 1 меньше каждого priceBreak. Потому что теперь в любом ответе все-равно можно будет перекидывать от одного заказчика к другому, пока не упремя или в priceBreak сверху, или в последнее количество с неменяемой ценой. И опять получается, что только один поставщик будет продавать не фиксированное в массиве значение.

Можно вместо ДП гнать симплекс метод, как Philipp уже написал (будет быстрее, если поставщиков мало, а количесто штук очень большое).

Возможно, можно ускорить решение в M раз, если вместо M разных ДП гнать одно со всеми поставщиками. Потом перебрать i<=n, распределить i штук по поставщикам беря только priceBreak, а потом прибавить остаток к поставщику с минимальной ценой (не переваливая за следующий priceBreak!). Но я не уверен, что это будет работать (не смог пока доказать, что, если у оптимального ответа урезать торчащий от priceBreak хвост у кого-то поставщика, то ответ останется оптимальным для нового количества).

Поменяйте < на > там, где у вас сравниваются элементы. Подсказка: у вас массив передан двумя int указателями. Т.е. сами элементы - это там где вы разименовываете какие-то указатели (это операция *что-то).

Простой вариант в реализации - перебирайте перестановку. Вот у вас в ответе буквам сопоставляются числа. Зафиксируйте порядок букв (вершин в одном графе). Тогда вершины второго графа (числа в ответе) будут представлять собой перестановку. Перебирайте все перестановки. Потом проверяйте, что одна матрица смежности после перестановки станет равна второй. Буквально для всех i, j проверяйте, что a[p[i]][p[j]] == b[i][j].

Перебор перестановок - известная задача. Применяйте этот алгоритм в цикле к текущей перестановке (которая изначально p[i] == i), пока получается. Реализация этого алгоритма уже есть в python.

Как только нашли перестановку, для которой матрицы совпали - выводите перестановку в ответ и вываливайтесь из перебора.

Чуть более сложный в реализации, но более быстрый - перестановки перебираются рекурсивной функцией с одного конца. При этом, по мере выбора нового элемента, сразу же производятся все проверки (вот, зафиксировали вы p[i] на i-ом уровне рекурсии, сразу же посмотрите, что для всех ja[p[i]][p[j]]==b[i][j] выполняются).

Как соберете всю перестановку (дойдете до n-ого уровня рекурсии) - вы нашли ответ.

Если реализация выдает неправильный ответ, попробуйте вместо условия a[p[i]][p[j]]==b[i][j] поменять на a[i][j]==b[p[i]][p[j]] (Тут сложно понять, прямую или обратную перестановку вы хотите в ответе).

Смотрим в документацию.

У шаблона std::priority_queue 3 параметра - тип элемента, контейнер и компаратор.
priority_queue хранит элементы в заданном контейнере, поддерживает там какую-то свою структуру (кучи) используя переданный компаратор для быстрой реализации операций приоритетной очереди.

Дефолтный контейнер - vector и компаратор стандартный std::less, поэтому работает просто priority_queue, например.

Вам может понадобится передавать свой какой-то контейнер, если вы хотите, например, аллокатор поменять. Или вы знаете, что в очереди будет почти всегда ровно K элементов, и вы передаете какой-то свой контейнер, который сразу же один раз выделяет K элементов.

Однако, если вам надо поменять только компаратор (третий параметр), то передать второй параметр тоже придется. Ну, вот перепутали порядок параметров разработчики стандарта. Нельзя задать компаратор, не задав и контейнер. Поэтому, надо писать там vector<> во втором параметре.

Edit. Там же в документации написано, что компаратор должен возвращать true, если первый элемент строго меньше второго. Ваш пример компаратора - похоже правильный. Однако, учтите, что очередь выдает сначала максимальный элемент. Т.е, если вам нужна очередь на минимум, то вам надо поменять знак в компараторе.

Алгоритм обхода в ширину или в глубину. Еще его называют алгоритм заливки. Гуглите. Если за одну заливку вы закрасили все черные пиксели, то фигура одна. Иначе, если компонент взязности несколько - разрыв есть.

Я так понял, надо распараллелить? Посмотрите на OpenMP - работает в С/C++. Параллеленье очень просто делается - вставляете какие-то директивы в код, ключи компиляции и все работает.

Как решать задачу паралелльно: Разбейте всю строку на N (количество потоков) частей и каждый поток отдельно для каждой части найдет ответ внутри нее. А также две велечины: Самый последний символ '<', самый первый симовл '<' и вообще, есть ли они в этом куске.

Потом непараллельная часть, которая выберет лучшый ответ из N кусоков, а также проверит, какой есть самый длинный ответ распределенный по кускам. Для этого у вас все есть - вы знаете в каждом куске какой символ может быть началом <...> идущий в следующие куски и какой может быть концом. Надо еще рассмотреть случай, что в данном куске последний < левее первого > - тогда из этого куска отрезок <...> торчать не может. Иначе смотрите, где может левее начаться отрезок. Это все реализуется одним циклом на N итераций. Надо хранить последний символ < в предыдущих кусках, который пока не закрыт. Или закрываете текущим куском и сравниваете с ответом, или обрываете его (если кусок начинается с <) или продолжаете отрезок в следующий кусок.

Вам равноудаленные или наиболее удаленные точки? Это немного разные вещи.

Равноудаленные точки - это надо пересекать "серединные перпендикуляры" для каждой пары заданных точек и смотреть, что решение одна и та же точка. Самые удаленные - это посмотреть на пересечения всех пар серединных перпендикуляров, перпендикуляров с границами области, вершины области. Из всех этих точек выбрать наиболее удаленные от всех заданных.

Теперь, что такое серединный перпендикуляр в манхеттанском расстоянии - это прямая, через середину отрезка между точками, строго под углом в 45 градусов. Соответственно, 2 таких перпендикуляра не могут пересечься.
Осталось только посмотреть пересечение таких прямых и границы области, и вершины области.

Эта функция не определена при x < 0 или 1-cos(x) = 0. Т.е. Если x < 0 или x= pi/2+2pi*k.

Ф программе вычисляйте функцию по шагам. Сначала знаменатель, если он оказался 0 - not defined. Иначе смотрите, что числитель можно вычислить (x>=0).

векторная формула: A + (B-A)/sqrt(|A-B|)*3

В числах
x = Ax+(Bx-Ax)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)
y = Ay+(By-Ay)*3/sqrt((Ax-Bx)^2+(Ay-By)^2)