Wataru

Везде, где можно использовать кучу, можно использовать и бинарное дерево поиска. Но, куча имеет несколько приемуществ. Грубо говоря, она работает быстрее и жрет меньше памяти.

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

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

Как-то сильно ускорить мне не удалось, но можно брать каждую точку одного полигона, строить 2 касательные на другой полигон и оставлять только те, которые одновременно являются касательными к первому полигону.
Это проверяется через векторные произведения веторов-сторон и вектора отрезка между полигонами. Отрезок между полигонами должен быть между двумя векторами сторон (если они ориентированны в одну сторону, скажем, против часовой стрелки). Это должно уже в почти в 4 раза уменьшить количество отрезков у вас.

Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.

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

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

Для двух переменных задача решается через расширенный алгоритм Евклида.

Решайте итеративно, добавляя новые переменные. Вот вы получили первые k переменных так что их сумма с коэффициентами равна GCD() коэффициентов. Пусть этот gcd(a1,a2,... ak) = d. Теперь решите тем же алгоритмом уравнение d*x + a(k+1)y = gcd(d,a(k+1)). y будет искомым значением последней переменной, а все предыдущие значения надо домножить на значение x.

В конце вы нашли GCD всех коэффициентов и вы можете проверить, что правая часть на него делится. если нет - решения нет. Если делится, то надо на результат деления домножить все переменные.

Да, тут еще спецэффект есть, что с отрицательными числами не работает GCD. Надо поменять знаки у коэффициентов, запомнить это и в конце поменять знаки у переменных назад.

Решение за O(n log M), где n - количество переменных, M - максимальное значение коэффициентов.

У вас порядок проверок нарушен.

Сначала надо проверить, что знаменатель не ноль, а только потом, что вся дробь неотрицательна.
Для проверки, что логарифм не берется из отрицательного числа надо проверить именно это (что выражение под логарифмом >=0). Вы же почему-то проверяете, что оно равно нулю.

И еще у вас выражение неправильно считается. Надо скобки расставить. (sqrt(X - 5 / X * X - 9) подсчитает корень из x минус 5, деленное на x^x, минус 9 - 3 слагаемых, из которых только второе дробь.

Итого вам надо:
- переставить местами условия, чтобы деление на 0 было первым.
- исправить условие на логарифм из отрицательного числа
- расставить скобки в выражении.

Куча не иницализированных локальных переменных. Эти переменные не обнуляются в языке Си. Там какой-то мусор. Может быть и 0, но это как повезет.
number - вы там присваиваете rotor[number] что-то, а чему оно равно? i в цикле, как Rsa97 сказал.

И вообще, вы с алгоритмом перемудрили. Вы случайно генерируете число, пока не найдете новое число в массиве.
Есть более элегантное решение:
Заполните массив числами от 0 до 74 подряд. Потом перемешайте его, как написанно в вики. Или можно совместить изначальное заполнение и перемешивание. Буквально, вся функция filling становится:

void filling(int rotor[], int randvalue)
{
  srand(randvalue);
  for(int i = 0; i < 75; ++i) {
    int j  = rand() % (i+1);
    rotor[i] = rotor[j];
    rotor[j] = i;
  }
}

Логика у вас правильная - взять середину отрезка 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 указателями. Т.е. сами элементы - это там где вы разименовываете какие-то указатели (это операция *что-то).