Geometric Algorithms IV

Geometric problems are hard (even when they are labeled as “medium” in LC). The complications arise primarily from the floating-point calculations, over and underflow, as well as the precise equations that one must come up with.

This problem Separate Squares I - LeetCode requires a binary search in space 10^9. For each iteration, we calculate the areas above and below. Hence the total time is of the order LogN * N. But there are a few things to keep in mind:

1/ Start by transforming all the input from int to double. This will avoid any over and underflow calculation

2/ Break down into smaller subroutines, for debugging

3/ Remember that when dealing with floating-points, to say that A == B, what you really need to do is ensure that |A – B| <= T where T is some threshold (in our case T = 0.00001)

You can use LLM such as OpenAI ChatGPT o1 (with advanced reasoning) for debugging. For example, you can ask it to plot some input in a Cartesian System for debugging purposes:

If you ask it to solve the problem, it actually does it well (not as fast as the binary search approach, it managed to solve in T(n) = 8nLogN + 20N, which is slower than the binary search approach suggested as a hint in the problem description).

Code works well, and it is shown below. Cheers, ACC

public double SeparateSquares(int[][] squares)
{
    double maxY = 0.0;
    double minY = 0.0;

    double[][] dSquares = new double[squares.Length][];
    for (int i = 0; i < dSquares.Length; i++)
    {
        dSquares[i] = new double[squares[i].Length];
        for (int j = 0; j < squares[i].Length; j++)
            dSquares[i][j] = (double)squares[i][j];
    }

    FindAreaBoundaries(dSquares, ref maxY, ref minY);

    double areaAbove = 0.0;
    double areaBelow = 0.0;

    double midY = 0.0;
    while (maxY > minY)
    {
        midY = (maxY + minY) / 2.0;
        //Console.WriteLine("{0}, {1}, {2}", minY, maxY, midY);
        CalculateSplitAreas(dSquares, midY, ref areaAbove, ref areaBelow);

        if (EqualDoubles(areaAbove, areaBelow) || EqualDoubles(maxY, minY))
            break;
        else if (areaAbove > areaBelow)
            minY = midY;
        else
            maxY = midY;
    }

    double retVal = double.MinValue;
    foreach (double[] square in dSquares)
    {
        if (square[1] <= midY && square[1] + square[2] >= midY)
            return midY;
        if (square[1] + square[2] < midY)
            retVal = Math.Max(retVal, square[1] + square[2]);
    }

    return retVal;
}

public bool EqualDoubles(double area1,
                        double area2)
{
    //Console.WriteLine(Math.Abs(area1 - area2));
    return Math.Abs(area1 - area2) <= (1.0 / 100000.0);
}
public void CalculateSplitAreas(double[][] squares,
                                double y,
                                ref double areaAbove,
                                ref double areaBelow)
{
    areaAbove = 0.0;
    areaBelow = 0.0;
    foreach (double[] square in squares)
    {
        double tempAreaAbove = 0.0;
        double tempAreaBelow = 0.0;
        CalculateSplitAreas(square, y, ref tempAreaAbove, ref tempAreaBelow);
        areaAbove += tempAreaAbove;
        areaBelow += tempAreaBelow;
    }
}

public void FindAreaBoundaries(double[][] squares,
                                ref double maxY,
                                ref double minY)
{
    maxY = Double.MinValue;
    minY = Double.MaxValue;
    foreach (double[] square in squares)
    {
        maxY = Math.Max(maxY, square[1] + square[2]);
        minY = Math.Min(minY, square[1]);
    }
}

public void CalculateSplitAreas(double[] square,
                                double y,
                                ref double areaAbove,
                                ref double areaBelow)
{
    if (square[1] > y)
    {
        areaBelow = 0.0;
        areaAbove = square[2] * square[2];
    }
    else if (square[1] + square[2] < y)
    {
        areaAbove = 0.0;
        areaBelow = square[2] * square[2];
    }
    else
    {
        areaAbove = (square[1] + square[2] - y) * square[2];
        areaBelow = (y - square[1]) * square[2];
    }
}