1.2.2

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

同样实现了一个 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)
                {
                    return -1;
                }
                else if (alen > blen)
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
        }
    }
}

Main 方法

namespace _1._2._2
{
    /*
     * 1.2.2
     * 
     * 编写一个 Interval1D 的用例,从命令行接受一个整数 N。
     * 从标准输入中读取 N 个间隔(每个间隔由一对 double 值定义)并打印出所有相交的间隔对。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Type the value of N:");
            int N = int.Parse(Console.ReadLine());
            List<Interval1D> intervalList = new List<Interval1D>();

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

            //读取并建立间隔数组
            Console.WriteLine("Type the data, make sure there is a space between two numbers.\nExample: 0.5 1");
            for (int i = 0; i < N; ++i)
            {
                string temp = Console.ReadLine();
                double lo = double.Parse(temp.Split(' ')[0]);
                double hi = double.Parse(temp.Split(' ')[1]);

                if (lo > hi)
                {
                    double t = lo;
                    lo = hi;
                    hi = t;
                }

                intervalList.Add(new Interval1D(lo, hi));
            }

            //判断是否相交并输出
            for (int i = 0; i < N; ++i)
            {
                for (int j = i + 1; j < N; ++j)
                {
                    if (intervalList[i].Intersect(intervalList[j]))
                    {
                        Console.WriteLine($"{intervalList[i].ToString()} {intervalList[j].ToString()}");
                    }
                }
            }
        }
    }
}

另请参阅

Geometry 库

上一题 下一题