Mrrl

А откуда взялась задача? Есть ли ссылка на оригинал? Есть ли там примеры?
Пока впечатление, что авторы хотели чего-то другого.

Совсем не факт, что рекурсивные алгоритмы медленнее. Я только что написал тестовый пример - перебор чисел, все цифры в которых различны. Рекурсивная форма работает примерно на 10% быстрее, чем нерекурсивная, и на её написание ушло в несколько раз меньше времени.

1) строите границы Г1, Г2.
2) для каждой считаете:
- центр масс (x0,y0)
- три интеграла: a11=int((x-x0)^2), a12=a21=int((x-x0)*(y-y0)), a22=int((y-y0)^2)
- собственные значения m1,m2 (m1 < m2) и собственные вектора v1,v2 матрицы ((a11 a12) (a21 a22)).
Пусть это было вычислено для Г1, а для Г2 получается m1', m2', v1', v2'.
Если искажений при повороте нет, то m1=m1', m2=m2'. Угол поворота определяется углом z между v1 и v1' (но надо сообразить, в какую сторону). К сожалению, он определён с точностью до 180 гр - так что надо будет как-нибудь сравнить варианты поворота на z и на z+180, и выбрать лучший. Допустим, что это z.
Осталось найти точку, при повороте вокруг которой на угол z точка (x0,y0) переходит в (x0',y0'). Проще всего записать это в комплексных числах: p0=x0+i*y0, p1=x0'+i*y0', f=exp(i*z). Если искомый центр c, то f*(p0-c)=p1-c, откуда c=(p1-f*p0)/(1-f).
И всё. Ничего сложного, первый курс ангема...

Если мы возьмём любую цепочку, проходящую через все точки (например, змейку или спираль), и разрежем её на куски всеми возможными способами, а потом часть кусков ещё и развернём, у нас уже получится примерно 2^(N^2)/3 вариантов. Уже при N=7 перечислить их нереально (при N=6 их всего 10 миллиардов - это не так много). Но поскольку исходных цепочек (проходящих через все точки) много, а кроме того, не все конфигурации можно получить разрезанием одной цепочки, вариантов будет ещё больше.
Алгоритмы - как рекурсия, так и перебор состояний клеток - не очень сложные. В обоих случаях нужно искать разбиение на неориентированные цепочки, а потом всеми способами задавать их направление.
В случае перебора состояний (он проще) делаем так. Замечаем, что у каждой клетки есть 10 возможных состояний - 4 для конца цепочки (направления, куда из этой клетки цепочка идёт), 4 для клетки, где цепочка поворачивает, и 2 для клетки, через которую она проходит прямо. Кроме того, есть ограничения: цепочка не может упираться в стенку, и общее ребро двух соседних клеток либо пересекается цепочкой с каждой стороны, либо нет. Ну, и не должно быть циклов.
Алгоритм получается таким. Перебираете клетки матрицы по строкам. Для каждой очередной клетки смотрите состояние её соседей, и получаете список возможных состояний самой клетки - их не более трёх. В случае, если есть состояние, которое соединяет две соседние цепочки, надо пройтись по ним - проверить, не являются ли они концами одной цепочки (если да - получится цикл, а он запрещён). Теперь подставляем в клетку по очереди все допустимые состояния, и рекурсивно вызываем функцию перебора для следующей клетки. Когда дойдём до конца - фиксируем найденное разбиение.

void PrintAllWords(string alphabet,int length){
  PrintAllWords(alphabet,length,"");
}
void PrintAllWords(string alphabet,int length,string prefix){
  if(length==0) Console.WriteLine(prefix);
  else foreach(char c in alphabet) PrintAllWords(alphabet,length-1,prefix+c);
}

Гамильтонов путь тут ни при чём - ведь нет запрета проходить одну вершину дважды? Но это в чистом виде задача коммивояжера. Тоже входит в класс NP. Точное решение будет слишком долгим, надо искать приближённые.

Довольно просто решить за O(N^3).
Пусть координаты k-го прямоугольника - (x1[k],x2[k],y1[k],y2[k]).
Берёте все x1,x2 (их 2*N штук), сортируете, выкидываете одинаковые. Это проекции вершин на ось X. Обозначим полученный массив A.
Аналогично с y1,y2 - получается массив B (тоже длиной не больше 2*N).
Теперь перебираем прямоугольники C=[A[p],A[p+1]]*[B[q],B[q+1]] для всех p,q. Ни один из них не пересекается сторонами исходных прямоугольников, так что если центр C лежит в одном из исходных прямоугольников, то весь прямоугольник принадлежит объединению, если нет - то не имеет с ним общих внутренних точек. Суммируем площади всех прямоугольников, принадлежащих объединению, и пишем ответ.
Можно соптимизировать до O(N^2). Насчёт O(N*log(N)) не знаю.

Сначала лучше перейти в систему координат, в которой стороны прямоугольника параллельны координатным осям, а центр - в точке (0,0): пусть при преобразовании (x,y) -> (p*x+q*y+r,-q*x+p*y+s) прямоугольник переходит в abs(X) <= A, abs(Y) <= B.
Пусть (X1,Y1) и (X2,Y2) - координаты вершин отрезка после преобразования.
Если max(X1,X2) < -A || min(X1,X2) > A || max(Y1,Y2) < -B || min(Y1,Y2) > B, то не пересекается: отрезок находится за одной из сторон прямоугольника.
В противном случае условием пересечения, насколько я понимаю, будет
abs(X1*Y2-Y1*X2) <= abs(A*(Y2-Y1)) + abs(B*(X2-X1))
Тщательно не проверял, но шансы, что формула правильная, хорошие.

Сначала учитываем 3*N^2 треугольников, у которых вершина с прямым углом лежит на одной из координатных осей (или вообще в точке (0,0)).
Теперь посчитаем все остальные треугольники.
Пусть (a,b) - координаты вершины с прямым углом, 0 < a <= N, 0 < b <= N.
Если c=НОД(a,b), a1=a/c, b1=b/c, то оставшаяся вершина должна иметь координаты (x,y)=(a+t*b1,b-t*a1), где t - ненулевое целое число.
Должны выполняться условия 0 <= x,y <= N. Перепишем их в виде условий на t:
-a/b1 <= t <= (N-a)/b1, -(N-b)/a1 <= t <= b/a1 (заметим, что a1, b1 больше нуля, так что делить можно). Учитывая, что t должно быть целым, оно лежит на отрезке от
t0 = -floor(min(a/b1,(N-b)/a1))
до
t1 = floor(min((N-a)/b1,b/a1))
И, поскольку запрещённое значение 0 всегда принадлежит этому отрезку, получаем, что число треугольников с вершиной (a,b) равно t1-t0.
Перебираем все точки (a,b), считаем t1-t0 и суммируем.
Всё. Сложность N^2*log(N), основное время тратится на вычисление НОД.
Если надо быстрее - надо будет думать. Скорее всего, надо будет перебирать взаимно простые пары (a1,b1), считать, сколько точек попало в перекошенный квадрат (переведённый в базис (a1,b1), (-b1,a1)), искать для них формулу и суммировать. Может быть, получится, может быть, нет. Какого порядка N?

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