2.5.25

2.5.25 #

解答 #

官方解答见：https://algs4.cs.princeton.edu/25applications/Point2D.java.html

这些比较器都以嵌套类的形式在 Point2D 中定义。

静态比较器直接在类中以静态成员的方式声明。

非静态比较器则需要提供工厂方法，该方法新建并返回对应的比较器对象。

代码 #

/// <summary>
/// 按照 X 顺序比较。
/// </summary>
private class XOrderComparer : Comparer<Point2D>
{
    public override int Compare(Point2D x, Point2D y)
    {
        if (x.X < y.X)
        {
            return -1;
        }

        if (x.X > y.X)
        {
            return 1;
        }

        return 0;
    }
}

/// <summary>
/// 按照 Y 顺序比较。
/// </summary>
private class YOrderComparer : Comparer<Point2D>
{
    public override int Compare(Point2D x, Point2D y)
    {
        if (x.Y < y.Y)
        {
            return -1;
        }
        if (x.Y > y.Y)
        {
            return 1;
        }

        return 0;
    }
}

/// <summary>
/// 按照极径顺序比较。
/// </summary>
private class ROrderComparer : Comparer<Point2D>
{
    public override int Compare(Point2D x, Point2D y)
    {
        var delta = (x.X * x.X + x.Y * x.Y) - (y.X * y.X + y.Y * y.Y);
        if (delta < 0)
        {
            return -1;
        }

        if (delta > 0)
        {
            return 1;
        }

        return 0;
    }
}

/// <summary>
/// 按照 atan2 值顺序比较。
/// </summary>
private class Atan2Order : Comparer<Point2D>
{
    private readonly Point2D _parent;

    public Atan2Order(Point2D parent)
    {
        _parent = parent;
    }
    public override int Compare(Point2D x, Point2D y)
    {
        var angle1 = _parent.AngleTo(x);
        var angle2 = _parent.AngleTo(y);
        if (angle1 < angle2)
        {
            return -1;
        }

        if (angle1 > angle2)
        {
            return 1;
        }
        return 0;
    }
}

/// <summary>
/// 按照极角顺序比较。
/// </summary>
private class PolarOrder : Comparer<Point2D>
{
    private readonly Point2D _parent;
    public PolarOrder(Point2D parent)
    {
        _parent = parent;
    }
        
    public override int Compare(Point2D q1, Point2D q2)
    {
        var dx1 = q1.X - _parent.X;
        var dy1 = q1.Y - _parent.Y;
        var dx2 = q2.X - _parent.X;
        var dy2 = q2.Y - _parent.Y;

        if (dy1 >= 0 && dy2 < 0)
        {
            return -1;
        }

        if (dy2 >= 0 && dy1 < 0)
        {
            return 1;
        }
        if (dy1 == 0 && dy2 == 0)
        {
            if (dx1 >= 0 && dx2 < 0)
            {
                return -1;
            }

            if (dx2 >= 0 && dx1 < 0)
            {
                return 1;
            }
            return 0;
        }
        return -Ccw(_parent, q1, q2);
    }
}

另请参阅 #

SortApplication 库