演算法（第四版）C#題解——1.2

寫在前面

整個項目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp

這一節內容可能會用到的庫文件有 Geometry 和 Commercial，同樣在 Github 上可以找到。

善用 Ctrl + F 查找題目。

習題 & 題解

練習（1.2.1~1.2.14）

1.2.1

題目

編寫一個 Point2D 的用例，從命令行接受一個整數 N。
在單位正方形中生成 N 個隨機點，然後計算兩點之間的最近距離。

解答

這裡自己實現了一個 Point2D 類（包含在了 Geometry 庫中）。

JAVA 版本參考：http://algs4.cs.princeton.edu/12oop/Point2D.java.html。

求最近兩點只需要反覆調用 Point2D 類中的 DistTo() 方法就可以了。

代碼

Point2D 類

/// <summary>
    /// Point2D 二維點類。
    /// </summary>
    public sealed class Point2D : IComparable<Point2D>
    {
        public readonly static Comparer<Point2D> X_Order = new XOrder();
        public readonly static Comparer<Point2D> Y_Order = new YOrder();
        public readonly static Comparer<Point2D> R_Order = new ROrder();

        public double X { get; }
        public double Y { get; }
        public int Radius { get; set; }

        public Point2D(double x, double y)
        {
            if (double.IsInfinity(x) || double.IsInfinity(y))
            {
                throw new ArgumentException("x, y must be finite");
            }

            if (double.IsNaN(x) || double.IsNaN(y))
            {
                throw new ArgumentNullException("Coordinate cannot be NaN");
            }

            this.X = x;
            this.Y = y;
            this.Radius = 2;
        }

        /// <summary>
        /// 返回極半徑。
        /// </summary>
        /// <returns></returns>
        public double R()
        {
            return Math.Sqrt(X * X + Y * Y);
        }

        /// <summary>
        /// 返回極角。
        /// </summary>
        /// <returns></returns>
        public double Theta()
        {
            return Math.Atan2(Y, X);
        }

        /// <summary>
        /// 返回兩個點之間的角度。
        /// </summary>
        /// <param name="that">要計算角度的另一個點。</param>
        /// <returns></returns>
        private double AngleTo(Point2D that)
        {
            double dx = that.X - this.X;
            double dy = that.Y - this.Y;
            return Math.Atan2(dy, dx);
        }

        /// <summary>
        /// 判斷 a,b,c 三個點的關係，如果 {順時針, 共線, 逆時針} 則返回 {-1, 0, 1}。
        /// </summary>
        /// <param name="a">第一個點。</param>
        /// <param name="b">第二個點。</param>
        /// <param name="c">第三個點。</param>
        /// <returns></returns>
        public static int CCW(Point2D a, Point2D b, Point2D c)
        {
            double area2 = (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
            if (area2 < 0)
                return -1;
            if (area2 > 0)
                return 1;
            return 0;
        }

        /// <summary>
        /// 返回 abc 三個點構成的三角形的面積的平方。
        /// </summary>
        /// <param name="a">第一個點。</param>
        /// <param name="b">第二個點。</param>
        /// <param name="c">第三個點。</param>
        /// <returns></returns>
        public static double Area2(Point2D a, Point2D b, Point2D c)
        {
            return (b.X - a.X) * (c.Y - a.Y) - (b.Y - a.Y) * (c.X - a.X);
        }


        /// <summary>
        /// 返回當前點到另一個點之間的距離。
        /// </summary>
        /// <param name="that">另一個點。</param>
        /// <returns></returns>
        public double DistanceTo(Point2D that)
        {
            double dx = this.X - that.X;
            double dy = this.Y - that.Y;

            return Math.Sqrt(dx * dx + dy * dy);
        }

        /// <summary>
        /// 返回當前點到另一個點之間的距離的平方。
        /// </summary>
        /// <param name="that">另一個點。</param>
        /// <returns></returns>
        public double DistanceSquareTo(Point2D that)
        {
            double dx = this.X - that.X;
            double dy = this.Y - that.Y;

            return dx * dx + dy * dy;
        }

        /// <summary>
        /// 繪製二維點。
        /// </summary>
        /// <param name="g">原點在左下方，y軸向上，x軸向右的畫布。</param>
        public void Draw(Graphics g)
        {
            g.FillEllipse(Brushes.Black, (int)X, (int)Y, Radius, Radius);
        }

        /// <summary>
        /// 實現 IComparable 介面。
        /// </summary>
        /// <param name="other">需要比較的另一個對象。</param>
        /// <returns></returns>
        public int CompareTo(Point2D other)
        {
            if (this.Y < other.Y)
                return -1;
            if (this.Y > other.Y)
                return 1;
            if (this.X < other.X)
                return -1;
            if (this.X > other.X)
                return 1;

            return 0;
        }

        /// <summary>
        /// 按照 X 順序比較。
        /// </summary>
        private class XOrder : 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 YOrder : 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 ROrder : Comparer<Point2D>
        {
            public override int Compare(Point2D x, Point2D y)
            {
                double 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 Point2D parent;
            public Atan2Order() { }
            public Atan2Order(Point2D parent)
            {
                this.parent = parent;
            }
            public override int Compare(Point2D x, Point2D y)
            {
                double angle1 = parent.AngleTo(x);
                double angle2 = parent.AngleTo(y);
                if (angle1 < angle2)
                {
                    return -1;
                }
                else if (angle1 > angle2)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        /// <summary>
        /// 按照極角順序比較。
        /// </summary>
        private class PolorOrder : Comparer<Point2D>
        {
            private Point2D parent;
            public PolorOrder() { }
            public PolorOrder(Point2D parent)
            {
                this.parent = parent;
            }
            public override int Compare(Point2D q1, Point2D q2)
            {
                double dx1 = q1.X - parent.X;
                double dy1 = q1.Y - parent.Y;
                double dx2 = q2.X - parent.X;
                double dy2 = q2.Y - parent.Y;

                if (dy2 >= 0 && dy2 < 0)
                {
                    return -1;
                }
                else if (dy2 >= 0 && dy1 < 0)
                {
                    return 1;
                }
                else if (dy1 == 0 && dy2 == 0)
                {
                    if (dx1 >= 0 && dx2 < 0)
                    {
                        return -1;
                    }
                    else if (dx2 >= 0 && dx1 < 0)
                    {
                        return 1;
                    }
                    else
                    {
                        return 0;
                    }
                }
                else
                {
                    return -CCW(this.parent, q1, q2);
                }
            }
        }

        /// <summary>
        /// 按照距離順序比較。
        /// </summary>
        private class DistanceToOrder : Comparer<Point2D>
        {
            private Point2D parent;
            public DistanceToOrder() { }
            public DistanceToOrder(Point2D parent)
            {
                this.parent = parent;
            }
            public override int Compare(Point2D p, Point2D q)
            {
                double dist1 = parent.DistanceSquareTo(p);
                double dist2 = parent.DistanceSquareTo(q);

                if (dist1 < dist2)
                {
                    return -1;
                }
                else if (dist1 > dist2)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        public Comparer<Point2D> Polor_Order()
        {
            return new PolorOrder(this);
        }

        public Comparer<Point2D> Atan2_Order()
        {
            return new Atan2Order(this);
        }

        public Comparer<Point2D> DistanceTo_Order()
        {
            return new DistanceToOrder(this);
        }

        public override bool Equals(object obj)
        {
            if (obj == this)
            {
                return true;
            }
            if (obj == null)
            {
                return false;
            }
            if (obj.GetType() != this.GetType())
            {
                return false;
            }
            Point2D that = (Point2D)obj;
            return this.X == that.X && this.Y == that.Y;
        }

        public override string ToString()
        {
            return "(" + X + ", " + Y + ")";
        }

        public override int GetHashCode()
        {
            int hashX = X.GetHashCode();
            int hashY = Y.GetHashCode();
            return 31 * hashX + hashY;
        }

Main() 方法：

namespace _1._2._1
{
    /*
     * 1.2.1
     * 
     * 編寫一個 Point2D 的用例，從命令行接受一個整數 N。
     * 在單位正方形中生成 N 個隨機點，然後計算兩點之間的最近距離。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine("Type the value of N:");
            int N = int.Parse(Console.ReadLine());
            List<Point2D> pointlist = new List<Point2D>();
            Random random = new Random();

            if (N <= 2)
            {
                Console.WriteLine("Make sure there are 2 points at least");
                return;
            }

            //random.NextDouble() 返回一個 0~1 之間的 double 值
            for (int i = 0; i < N; ++i)
            {
                double x = random.NextDouble();
                double y = random.NextDouble();
                pointlist.Add(new Point2D(x, y));
            }

            double min = pointlist[0].DistanceTo(pointlist[1]);
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    double temp = pointlist[i].DistanceTo(pointlist[j]);
                    Console.WriteLine($"Checking Distance({i}, {j}): {temp}");
                    if (temp < min)
                    {
                        min = temp;
                    }
                }
            }

            Console.WriteLine($"\nThe minimal distance is {min}");
        }
    }
}

1.2.2

題目

編寫一個 Interval1D 的用例，從命令行接受一個整數 N。
從標準輸入中讀取 N 個間隔（每個間隔由一對 double 值定義）並列印出所有相交的間隔對。

解答

同樣實現了一個 Interval1D 類（位於 Geometry 庫）。

JAVA 版本參考：http://algs4.cs.princeton.edu/12oop/Interval1D.java.html。

直接調用其中的 Intersect() 方法即可

代碼

Interval1D 類：

namespace Geometry
{
    /// <summary>
    /// 一維閉區間。
    /// </summary>
    public class Interval1D
    {
        public static readonly Comparer<Interval1D> Min_Order = new MinEndpointComparer();
        public static readonly Comparer<Interval1D> Max_Order = new MaxEndpointComparer();
        public static readonly Comparer<Interval1D> Length_Order = new LengthComparer();

        public double Min { get; }
        public double Max { get; }

        /// <summary>
        /// 構造函數。
        /// </summary>
        /// <param name="lo">一維區域的下界。</param>
        /// <param name="hi">一維區域的上界。</param>
        public Interval1D(double lo, double hi)
        {
            if (double.IsInfinity(lo) || double.IsInfinity(hi))
            {
                throw new ArgumentException("Endpoints must be finite");
            }
            if (double.IsNaN(lo) || double.IsNaN(hi))
            {
                throw new ArgumentException("Endpoints cannot be NaN");
            }

            if (lo <= hi)
            {
                this.Min = lo;
                this.Max = hi;
            }
            else
            {
                throw new ArgumentException("Illegal interval");
            }
        }

        /// <summary>
        /// 一維區域的長度。
        /// </summary>
        /// <returns>返回長度。</returns>
        public double Length()
        {
            return this.Max - this.Min;
        }

        /// <summary>
        /// 判斷目標區間是否被本區間包含。
        /// </summary>
        /// <param name="that">需要判斷是否被包含的區間。</param>
        /// <returns></returns>
        public bool Contains(Interval1D that)
        {
            return this.Min < that.Min && this.Max > that.Max;
        }

        /// <summary>
        /// 目標值是否處在區域內。如果目標值在區域內則返回 True，否則返回 False。
        /// </summary>
        /// <param name="x">需要判斷的值。</param>
        /// <returns></returns>
        public bool Contains(double x)
        {
            return x >= this.Min && x <= this.Max;
        }

        /// <summary>
        /// 判斷兩個區域是否相交。
        /// </summary>
        /// <param name="that">需要判斷相交的另一個區域。</param>
        /// <returns>如果相交則返回 True，否則返回 False。</returns>
        public bool Intersect(Interval1D that)
        {
            if (this.Max < that.Min || that.Max < this.Min)
                return false;

            return true;
        }

        /// <summary>
        /// 繪製一維區間。
        /// </summary>
        /// <param name="g">原點在左下方，y軸向上，x軸向右的畫布。</param>
        /// <param name="y">繪製一維區間的 y軸 坐標。</param>
        public void Draw(Graphics g, int y)
        {
            Point A = new Point((int)Min, y);
            Point B = new Point((int)Max, y);
            g.DrawLine(Pens.Black, A, B);
        }

        /// <summary>
        /// 將區域轉換為 string，返回形如 "[lo, hi]" 的字元串。
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            string s = "[" + this.Min + ", " + this.Max + "]";
            return s;
        }

        /// <summary>
        /// 判斷兩個區間是否相等。
        /// </summary>
        /// <param name="obj">相比較的區間。</param>
        /// <returns></returns>
        public override bool Equals(object obj)
        {
            if (obj == this)
            {
                return true;
            }
            if (obj == null)
            {
                return false;
            }
            if (obj.GetType() != this.GetType())
            {
                return false;
            }
            Interval1D that = (Interval1D)obj;
            return this.Min == that.Min && this.Max == that.Max;
        }

        /// <summary>
        /// 返回區間的哈希代碼。
        /// </summary>
        /// <returns></returns>
        public override int GetHashCode()
        {
            int hash1 = Min.GetHashCode();
            int hash2 = Max.GetHashCode();
            return 31 * hash1 + hash2;
        }

        private class MinEndpointComparer : Comparer<Interval1D>
        {
            public override int Compare(Interval1D a, Interval1D b)
            {
                if (a.Min < b.Min)
                {
                    return -1;
                }
                else if (a.Min > b.Min)
                {
                    return 1;
                }
                else if (a.Max < b.Max)
                {
                    return -1;
                }
                else if (a.Max > b.Max)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        private class MaxEndpointComparer : Comparer<Interval1D>
        {
            public override int Compare(Interval1D a, Interval1D b)
            {
                if (a.Max < b.Max)
                {
                    return -1;
                }
                else if (a.Max > b.Max)
                {
                    return 1;
                }
                else if (a.Min < b.Min)
                {
                    return -1;
                }
                else if (a.Min > b.Min)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }

        private class LengthComparer : Comparer<Interval1D>
        {
            public override int Compare(Interval1D a, Interval1D b)
            {
                double alen = a.Length();
                double blen = b.Length();

                if (alen < blen)
                {