Wataru

У вас решение за O(NM), когда как есть решение за O(N+M).

Вы считаете сумму всех цен каждый раз. Но это делать не обязательно, ведь вам надо найти сумму всех цен, кроме одной. Можно подсчитать сумму всех один раз и потом вычитать из нее лишнюю цену (но надо аккуратно подумать о переполнениях). Или можно воспользоватся префиксными и постфиксными суммами.

Сначала каждую строку resize до размера size()+w0+w1. Потом сдвигайте элементы на w0 позиций вправо (цикл надо гнать с конца). Потом заполните пустые места нулями.

То же самое в самом векторе векторов. Только вместо чисел надо сдвигать вектора на h0 позиций. На пустые места надо будет записывать std::vector(n+w0+w1, 0);

Edit: А вообще, тут и добавлять в массив ничего не надо. Вы нужный вам ответ можете нулями прямо во время вывода добить.

Я предполагаю, что условие вашей задачи такое - дано куча запросов вида <начало отрезка, конец, значение>. Все ячейки в этом отрезке заполняются заданным значением, если они меньше его. Надо найти сумму всех ячеек в конце.

Тут есть два решения. Первое - через дерево отрезков с отложенным изменением. Само дерево немного странное получается, потому что оно ничего не считает в промежуточных вершинах, а будет только хранить отложенное изменение. Физический смысл отложенного изменения - "все ячейки в этом поддереве должны быть не меньше этого значения". Релаксация (спуск вниз) отложенного изменения происходит так: отложенное изменение в детях заменяется на максимум из того, что там лежит и отложенного значения в родителе. Значение в родителе заменяется на 0. При запросе спускайтесь рекурсивно по дереву, релаксируя изменения, пока текущее поддерево не будет целиком лежать в запросе. Тогда перезаписывайте отложенное значение в текущей вершине, если оно меньше. В конце обработки запросов релаксируйте все вершины сверху вниз и просуммируйте значения в листьях.

Второе решение - через метод сканирующей прямой может быть проще в реализации из-за наличия встроенных структур данных. Я думаю, в питоне должна быть структура, которая умеет быстро добавлять число, удалять число и брать максимум из всех чисел. В C++ есть std::set или std::priority_queue.
Для каждого отрезка-запроса создайте два события вида <координата, отрезок открылся/закрылся, значение> (разберитесь, где там +-1 поставить так, чтобы длина отрезка по координатам равнялась количеству покрытых ячеек). Засуньте их все в один массив и отсортируйте по координате. Потом проходитесь слева-на-право. Применяйте текущее событие - или добавляйте число в вашу структуру данных, или удаляйте оттуда. Между текущим и следующим событием по координатам все ячейки покрыты одним и тем же множеством отрезков, поэтому можно их все быстро посчитать, ведь ваша структура умеет брать максимум. Добавляйте к ответу разность координат между текущим и следующим событиями, умноженную на значение максимума из структуры. Все.

FillPolygon работает через обход в ширину.

Сначала одним циклом покрасьте все точки контура.
Потом берите любую точку внутри полигона, красьте ее и кладите в очередь. Пока очередь не пуста берете точку оттуда, берете 4 или 8 ее соседей и если они не покрашены еще - красите их и кладете в очередь.

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

if ((matrix[i][j] < minValue[j]) && (isPartOfOutputTree[j] == false))

Вот тут ошибка. Ведь i - это номер итерации,а совсем не только что включенная в дерево вершина, относительно которой надо сделать релаксацию.

Шансы 1:3:3:1. Генерируйте случайное число от 0 до 7. При 0 - выдавайте случайное число < 50. При 1-3 - случайное число от 50 до 74, при 4-6 - выдывайте ответ от 75 до 89, при 7 выдавайте число от 90 до 100.

Какие именно числа из промежутка выдавать в задании не сказано. Можете как-то случайно равновероятно или как-то нормально генерировать или вообще выдывать середину промежутка всегда.

Через битовые операции вы ничего не сделаете, потому что у вас, судя по всему, надо найти общие цифры в десятичной системе счисления. Вообще найти десятичные цифры у вещественных чисел - весьма сложная операция.

Я думаю, вам остается только вывести оба числа в строки в каком-нибудь фиксированном формате и дальше сравнивать посимвольно.

Есть алгоритм за O(n log n), где n - количество точек в кривой.

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

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

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

Удобно это реализовывать, если взять углы наклона всех сторон оболочки, их же сдвинутые на 90, 180 и 270 градусов и отсортировать. Далее надо перебирать рамки с такими углами наклона певрой стороны (можно в пределах [0,90) градусов). Первую рамку найдите перебором, а дальше какие-то точки надо будет сдвигать.

Итак, весь алгоритм:
1) построить выпуклую оболочку
2) добавить в массив углы всех сторон и их копии повернутые на 90, 180 и 270 градусов и отсортировать, но не добавлять углы не в [0,90).
3) для первого угла в массиве найдите 4 точки касания рамки.
4) Для каждого отрезка углов в отсортированном массиве проверить, а надо ли сдвинуть точки касания вперед (каждую из четырех точек со своим углом), потом найти площадь рамки в известных точках с известным наклоном.

Вместо работы с углами, для чего нужны тригонометрические функции, можно работать с векторами на единичной окружности. На отрезке углов можно легко взять середину, просто сложив два вектора-границы и нормировав. Для тернарного поиска не обязательно брать 1/3 и 2/3 на отрезке, поэтому можно так же просто просуммировать вектора с коэффициентами 1 и 2 и опять нормировать (v1+2*v2). Сортировать по углу тоже можно сравнивая вектора через векторное произведение векторов (иногда его называют псевдоскалярным).

Чтобы найти рамку с заданным углом на точках не надо ничего пересекать (кроме ответа в конце, если вам надо координаты рамки вывести, а не только площадь найти). Надо представить прямые в виде cosa*x + sina*y + c = 0. Отсюда, зная точку (x, y) и угол прямой (a), можно найти c. cosa и sina считать не надо - это координаты вектора, перпендикулярного к известному вектору наклона прямой. Когда вы нашли два значения c для двух параллельных сторон, эти коэффициенты можно сложить - это и будет расстояние между сторонами (надо складывать, потому что cosa и sina в этих двух прямых будут с разными знаками, ведь у одной прямой угол на пол оборота больше). Остается подсчитать это два раза для перпендикулярных прямых и перемножить.

Код для пересечения прямых в конце можно посмотреть тут.

До 15 точек можно полным перебором сделать. Вам надо перебрать все разбиения 3n точек на тройки. Таких разбиений (3n)!/(3!)^n/n! для n=5 - это чуть больше миллиона.

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

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

Какое-то геометрическое решение в голову что-то не приходит.