Wataru

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

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

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

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

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

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

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

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

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

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

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

Немного оффтоп. Для каждого фиксированного i не надо перебирать все j, в поисках того, где i*j=n. Достаточно проверить, что n делится на i без остатка: if (n%i == 0). Тогда j = n/i. Не будет никакого переполнения, которое, как вам longclaps уже ответил(а) привеодит к неверным результатам.

Еще вариант - можно гнать оба цикла до ceil(sqrt(n)). И выводить сразу 2 пары (i,j) и (j,i), если i!=j. потому что из двух множителей хотя бы один не больше корня n, иначе бы перемножение было бы больше n. И еще отдельно надо вывести варианты (1, n) И (n, 1).

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

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

Есть сложное, но более быстрое решение задачи - с помощью заметающей прямой. Подробно описанно вот тут: e-maxx.ru/algo/intersecting_segments
Работает за O(n log n), где n - количество отрезков. Его, правда, придется чуть-чуть подкорректировать, чтобы не учитывать пересечения соседних отрезков.