Размещение трапеций на ленте с нулевым отходом

Имеется n трапеций с одинаковой высотой. Площадь отхода - площадь треугольника, отсекаемого при присоединении одной трапеции к другой или к началу/концу ленты.

Задача - разработать алгоритм для минимизации площади отходов при размещении трапеций на ленте. Я рассматриваю в упрощенном варианте, когда нужно найти размещение, для которого площадь отходов будет 0.

Трапеции (ABCD) задаются тремя числами:

• Bx - x координата точки B
• Cx - x координата точки C
• Dx - x координата точки D

Точка A всегда (0, 0)

Пример входного файла:

n
b1x c1x d1x
...
bnx cnx dnx

Example:
10
-100 0 500
-900 -100 500
-1400 -400 500
-500 -400 500
-900 -400 500
-1300 500 500
0 400 500
-800 -800 500
-900 -900 500
-600 -300 500

Я написал рекурсивный алгоритм, но он работает медленно, при большом кол-ве трапеций. Для 1000 трапеций уже очень долго считает.

Program.cs

using Minimization;

const int h = 10;

decimal StartArea(int bx) => Math.Abs(bx) * h / 2;

decimal EndArea(int cx, int dx) => Math.Abs(cx - dx) * h / 2;

decimal Area(int cx, int dx, int bx) => (cx < dx && bx < 0) || (cx > dx && bx > 0) ?
        (Math.Abs(cx - dx) - Math.Abs(bx)) * h / 2 :
        (Math.Abs(cx - dx) + Math.Abs(bx)) * h / 2;

var path = @"c:\tests\9.txt";

var trapezoids = FileUtilities.GetTrapezoids(path);

HashSet<(int bx, int cx, int dx, int index)> startCandidates = new();

for (var i = 0; i < trapezoids.Length; i++)
{
    if (StartArea(trapezoids[i].bx) == 0)
        startCandidates.Add((trapezoids[i].bx, trapezoids[i].cx, trapezoids[i].dx, i));
}

var candidates = new Dictionary<int, HashSet<int>>();

for (var i = 0; i < trapezoids.Length; i++)
{
    candidates[i] = new HashSet<int>();
    for (var j = 0; j < trapezoids.Length; j++)
    {
        if (i == j) continue;
        if (Area(trapezoids[i].cx, trapezoids[i].dx, trapezoids[j].bx) == 0)
            candidates[i].Add(j);
    }
}


int[] res = null;

foreach (var (bx, cx, dx, index) in startCandidates)
{
    res = new int[trapezoids.Length];
    var currentPlace = 0;

    var currentIndex = index;
    res[currentPlace] = currentIndex;
    currentPlace++;

    res = PossibleList(currentPlace, res.AsSpan(), trapezoids);

    if (res != null)
        break;
}

int[]? PossibleList(int currentPlace, Span<int> span, Span<(int bx, int cx, int dx)> trapezoids)
{
    var currentIndex = res[currentPlace - 1];

    var nextCandidates = Except(candidates[currentIndex], span, currentPlace);

    if (nextCandidates.Count == 0)
        if (currentPlace == trapezoids.Length && EndArea(trapezoids[currentIndex].cx, trapezoids[currentIndex].dx) == 0)
            return span.ToArray();
        else
            return null;

    foreach (var candidate in nextCandidates)
    {
        span[currentPlace] = candidate;

        var possible = PossibleList(currentPlace + 1, span, trapezoids);

        if (possible != null)
            return possible;
    }

    return null;
}

HashSet<int> Except(HashSet<int> candidates, Span<int> span, int currentPlace)
{
    var res = new HashSet<int>();

    foreach (var candidate in candidates)
        if (!span[..currentPlace].Contains(candidate))
            res.Add(candidate);

    return res;
}

FileUtilities.cs

namespace Minimization
{
    /// <summary>
    /// Утилиты для работы с файлами
    /// </summary>
    public static class FileUtilities
    {
        public static Span<(int bx, int cx, int dx)> GetTrapezoids(string path)
        {
            using var sr = new StreamReader(path);

            var n = int.Parse(sr.ReadLine()!);

            var res = new (int bx, int cx, int dx)[n];

            for (var i = 0; i < n; i++)
            {
                var str = sr.ReadLine();
                var splitted = str!.Split();
                res[i] = (int.Parse(splitted[0]), int.Parse(splitted[1]), int.Parse(splitted[2]));
            }

            return res.AsSpan();
        }
    }
}

Как можно оптимизировать алгоритм? Думаю попробовать применить стек, но не очень представляю, как обойтись без рекурсии.