Wataru

Эта программа не будет работать на таких многоугольниках. Там есть комментарий:

/* this works only if all of the following are true:
...
* 4. poly is convex (implying 3).

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

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

Алгорим выделения замкнутых областей:

Строим ориентированный граф, где вершины - вершины полигонов (+ точки пересечения), а ребра - направленные отрезки (вместо каждого отрезка создаем два ребра в обе стороны между вершинами - концами отрезка).

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

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

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

Потом для всех областей проверяем, что там все ребра правильной ориентации (по часовой стрелке, как и у изначальных полигонов). Если совпало - то эта область - пересечение полигонов.

Это не работает, если полигоны не пересекаются. Тогда надо проверить любую точку каждого, содержися ли она целиком во втором полигоне.

Сначала переведите картинку из залачи в числа. Вот есть у вас 20 точек, пронумерованные от 1 до 20, как-то. Выпишите все 12 групп (9 окружностей и 3 диаметра). Будет у вас 12 наборов по 5-6 номеров. Запишите их в программе константными массивами.

Затем делайте перебор рекурсией: У вас в глобальном массиве или списком в параметре будет набор пока не поставленных чисел. Сначала проверьте, что вы не сделали уже 2 группы с разной суммой. Пройдитесь по всем 9+3 группам, если какая-то целиком уже заполнена, то записываете ее сумму в переменную для окружности или диаметра, соответственно. Если перед записью там уже была другая сумма -то вы нашили противоречие. В этом случае надо просто вернуться из текущей рекурсии назад.

Если противоречий нет и вы все 20 чисел поставили - выводите ответ.

Иначе - перебираете, какое число ставите в первую незаполненую точку циклом. Ставите туда число и вызываетесь рекурсивно.

Надо только аккуратно уже поставленные на картинке числа в нужные места поставить. Для этого их, во первых, не включйте в список непоставленных чисел, во вторых на заполенные позиции ставьте уже записанное там число.

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

Ваше решение не работает на примере 3,4,1,2. Тут нельзя удалить одно число, но ваша программа вернет true.

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

Мне кажется, надо статистику пересчитывать за константное время при вводе каждого нового числа. При запросе выдвавть последнюю статистику. Если часть чисел задана изначально, то придется подсчитать статистику для них за O(n), по другому никак - ведь все числа придется хоть раз просмотреть.

Надо для каждой вершины хранить предыдущую. Запишите это значение, когда кладете вершину в очередь. Для вершины (row, col) у вас в коде предыдущая (pt.x, pt.y).

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

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

Так же как со временной сложностью - количеством операций. Только считайте количество используемых байт.

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

Получаете какую-то формулу типа 10*n+16*m+n*m/2 + 100500*log n. Дальше применяете ассимптотический анализ.

Например, алгоритм DFS. есть граф с n вершинами и m ребрами. Пусть задан в виде списков инцидентности.

Тогда у вас есть n списков, которые все вместе содержат m элементов. Т.е. ваши входные данные занимают n*8+m(4+8) байт. n указателей на начало списка и m элементов - каждый содержит значение и указатель. Но не надо так считать досканально каждый байт, можно просто прикинуть n+m.

Сам алгоритм еще требует массива для пометок пройденных вершин: +n к потреблению памяти.

Функция требует сколько-то локальных переменных и параметров. Их несколько и от n или m это не зависит. В рекурсии функция может выть вызвана n раз, если вы все вершины пройдете вглубь. Итого на стеке эти функции съедят n*C, где С - какая-то константа.

Суммарная пространственная сложность n+m+n*C. Или O(n+m).

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

Доказательство по индукции. Для одной или двух вершин всегда будет 1 в D.

Пусть degree(v) - количество вершин, инцидентных v.
Лемма: В турнире с n вершинами будет хотя бы одна с degree() >= (n-1)/2. Иначе, просуммируем все degree().
С одной стороны, сумма будет равна количеству ребер, т.е. n(n-1)/2. С другой, эта сумма < n*(n-1)/2 по предполоджению. Противоречие, значит существует v: degree(v) >= (n-1)/2

Теперь докажем основное утверждение.
Рассмотрим турнир с n>2 вершинами. Там есть хотя бы одна v: degree(v) >= (n-1)/2. Включим ее в D. и удалим из графа ее и все, которым она инцедентна. Мы удалили из графа не меньше 1+(n-1)/2 вершин, фактически уполовинив количество вершин в графе. По индукционному предположению там надо log(n/2) вершин в доминирующем множестве. Иы добавили к ней 1. Поэтому в итоге нам надо log(n) вершин и для этого графа.

Это же доказательство можно использовать для построения D - включайте жадно самую крутую вершину в турнире и удаляйте ее и все ею доминируемое.

Динамическое программирование:
F(a,b,r) = может ли число составленное из a едениц и b нулей давать остаток r при делении на N.
База: F(0,0,0) = true, F(0,0,r) = false.

Пересчет: Итеративный пересчет такой - F(a,b,r) => то F(a+1,b,(2*r+1) % N) и F(a,b+1,(2*r+1) % N) Тут мы знаем, что есть число, дающее остаток r из a едениц и b нулей. Если мы к нему припишем в конец 1, то остаток будет (2*r+1)%N, а единиц будет на одну больше. Также почти можно приписать 0.

Для рекурсивного надо сначала избавится от всех степеней 2 в N (просто подсчитайте степень, вычтите это из B, поделите N на все двойки - В числе в конце обязательно должно стоять столько нулей).

Теперь можно найти x такое, что 2x = 1 (mod N) - обратное к 2 по модулю N. Смотрите расширенный алгоритм Эвклида для этого.

Дальше можно вычислять так (N - нечетное):
F(a,b,r) = F(a-1,b, (r-1)*x % N) || F(a, b-1, r*x % N).

Объяснение тут тоже простое - число или оканчивается на 0 или на 1. Попробуем оба варианта и сотрем последнюю цифру. Оставшееся число должно давать остаток (r-1)*x % N или r*x % N соответственно.

Ответ: Если F(A,B,0) - true, то число делящееся на N есть. Для нахождения числа надо дополнительно запоминать, какие цифры приписывались к чисам при рассчетах выше.

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

Таким образом можно выделить все замкнутые области на картинке.

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

2 варианта:
1) сделать новый массив с pair, записать туда элементы с двух массивов, отсортировать.
2) завести новый массив, забить его числами от 0 до n-1. Передать sort свою функцию сортировки, которая сравнивает не переданные числа a и b, а элементы перовго массива по этим индексам (array1[a] и array1[b]). После полученый набор индексов использовать для вывода второго массива (если сортировали массив indices, то выводите array2[indices[i]], для i от 0 до n-1).

Во первых, определите, что линии лежат на одной плоскости и не паралельны.
Обозначим точки первой прямой как A1 и B1, а второй - A2 и B2.

Введем вектора D1 = B1-A1 и D2 = B2-A2. Введем векторное уравнение.

D1*t + D2*r + (A1-A2) = 0.

Тут 2 неизвестные t и r, 3 уравнения (расписать по x, y и z).

Если система уравнений решается, то точка пересечения A1+D1*t или A2 - D2*r.

Тут правда предется повозиться со случаями. Надо попробовать решить систуму только для x, y, потом проверить в z. Если не получилось, то еще надо попробовать решить в x, z, потом поробовать подставить полученные r и t в у.

В коде ошибка. Прибавлять к sum надо делитель а не 1 каждый раз (sum=sum+i, а не +1).
Во вторых, можно цикл гнать до n/2 (включительно) а не до n. В блок-схеме у вас так и написано, но в коде не так.

Еще совет - начните if с новой строки после цикла. То как у вас if на той же строке что и закрывающая скобка от for - очень путает. И заодно, добавьте отступы внутри if внутри for (строка с прибавлением к sum).

Вот пример такого хеша:

int hash(string s) {
  return 42;
}

Можно вместо 42 возвращать другое число, но обязательно, всегда одно и то же.
Это все потому, что множества слов с ошибками перекрываются. Например, строки "aaaa" и "aabb" должны давать одинаковый хеш. Но точно так же сроки "bbbb" и "aabb" должны давать одинаковый хеш. В итоге получается, что все возможные строки должны давать одинаковый хеш.

В чем состоит изначальная задача? Зачем вам такой хеш понадобился? Наверняка что-то типа поиска строк, совпавших с 1-2 ошибками. В этом случае следует перебором сгенерировать из заданной строки все возможные с 1-2 ошибками, эти строки уже сохранить как-то (например, используя стандартный хеш в хеш-таблице).

Или можно сравнивать строки парами, считая сколько нужно ошибок, чтоб получить из одной строки другую. Это стандартное динамическое программирование. Гуглите дистанцию редактирования.