using System;
using System.Drawing;
 
namespace Geometry
{
    class Program
    {
        static void Main(string[] args)
        {
            Pattern[] patternList = new Pattern[10000];
 
            // Initialize patternList
            Random r = new Random();
            for (int i = 0, cpt = patternList.Length; i < cpt; )
            {
                patternList[i++] = new Circle(new Point(r.Next(10000), r.Next(10000)), r.Next(50));
                Point basePoint = new Point(r.Next(10000), r.Next(10000));
                patternList[i++] = new Quadrilateral(new Point(basePoint.X - r.Next(20), basePoint.Y - r.Next(20)), new Point(basePoint.X + r.Next(20), basePoint.Y - r.Next(20)), new Point(basePoint.X - r.Next(20), basePoint.Y + r.Next(20)), new Point(basePoint.X + r.Next(20), basePoint.Y + r.Next(20)));
            }
 
            // Check overrides
            for (int i = 0, cpt = patternList.Length; i < cpt - 1; i++)
            {
                for (int j = i + 1; j < cpt; j++)
                {
                    try
                    {
                        if (patternList[i].CheckOverride(patternList[j], true, true, true))
                        {
                            Console.WriteLine("{0} {1} overrides {2} {3}.", patternList[i].GetType().Name, i, patternList[j].GetType().Name, j);
                        }
                    }
                    catch (NotImplementedException ex)
                    {
                        Console.WriteLine("{0} {1} might override {2} {3}, but not checked (\"{4}\" ).", patternList[i].GetType().Name, i, patternList[j].GetType().Name, j, ex.Message);
                    }
                }
            }
            Console.ReadKey();
        }
    }
 
    abstract class MathTools
    {
        /// <summary>
        /// Checks if the point A is inside the retangle defined by P1 and P2
        /// </summary>
        /// <param name="A">Point to check</param>
        /// <param name="P1">Upper left corner of the rectangle</param>
        /// <param name="P2">Lower right corner of the rectangle</param>
        /// <returns>Flag indicating if the point is included in the rectangle</returns>
        public static bool PointInRectangle(Point A, Point P1, Point P2)
        {
            // First, we eliminate basic cases
            if (A.X < P1.X) return false; // A is at the left of the rectangle
            if (A.X > P2.X) return false; // A is at the right of the rectangle
            if (A.Y < P1.Y) return false; // A is at the top of the rectangle
            if (A.Y > P2.Y) return false; // A is at the bottom of the rectangle
 
            if (A.X <= P2.X && A.X >= P1.X && A.Y <= P2.Y && A.Y >= P1.Y) return true; // A is inside the rectangle
 
            return false; // A is outside
        }
    }
 
    abstract class Pattern
    {
        public Point BoundingBox1, BoundingBox2;
 
        /// <summary>
        /// Check if a pattern overrides this one.
        /// </summary>
        /// <param name="otherPattern">Other pattern that may override this one</param>
        /// <param name="optim1">Use bounding boxes optimization</param>
        /// <param name="optim2">Use circles distances optimization</param>
        /// <param name="optim3">Use point in circle optimization</param>
        /// <returns></returns>
        public bool CheckOverride(Pattern otherPattern, bool optim1, bool optim2, bool optim3)
        {
            // Step 1 : Check bounding boxes (optim1)
            if (optim1)
            {
                if (!MathTools.PointInRectangle(this.BoundingBox1, otherPattern.BoundingBox1, otherPattern.BoundingBox2) && !MathTools.PointInRectangle(this.BoundingBox2, otherPattern.BoundingBox1, otherPattern.BoundingBox2))
                {
                    // Bounding boxes are not overriding
                    return false;
                }
            }
 
            // Step 2 : If both patterns are circles it's very easy to check they are overriding
            if (optim2)
            {
                if (this.GetType() == typeof(Circle) && otherPattern.GetType() == typeof(Circle))
                {
                    Circle c1, c2;
                    c1 = this as Circle;
                    c2 = otherPattern as Circle;
                    if (Math.Pow(c1.Radius + c2.Radius, 2) >= (Math.Pow(c1.Center.X - c2.Center.X, 2) + Math.Pow(c1.Center.Y - c2.Center.X, 2))) return true;
                    return false;
                }
            }
 
            // Step 3 : If one of the pattern is a circle and the other one is a quadrilateral, it's easy to see if a top is included in the circle
            if (optim3)
            {
                Circle c;
                Quadrilateral q;
                if (this.GetType() == typeof(Circle) && otherPattern.GetType() == typeof(Quadrilateral))
                {
                    c = this as Circle;
                    q = otherPattern as Quadrilateral;
                }
                else if (this.GetType() == typeof(Quadrilateral) && otherPattern.GetType() == typeof(Circle))
                {
                    c = otherPattern as Circle;
                    q = this as Quadrilateral;
                }
                else
                {
                    c = null;
                    q = null;
                }
 
                if (c != null && q != null)
                {
                    double r2 = Math.Pow(c.Radius, 2);
                    if (
                        r2 >= Math.Pow(c.Center.X - q.PointA.X, 2) + Math.Pow(c.Center.Y - q.PointA.Y, 2) ||
                        r2 >= Math.Pow(c.Center.X - q.PointB.X, 2) + Math.Pow(c.Center.Y - q.PointB.Y, 2) ||
                        r2 >= Math.Pow(c.Center.X - q.PointC.X, 2) + Math.Pow(c.Center.Y - q.PointC.Y, 2) ||
                        r2 >= Math.Pow(c.Center.X - q.PointD.X, 2) + Math.Pow(c.Center.Y - q.PointD.Y, 2)
                    ) return true;
                }
            }
 
            // Step 4 : We are sure the patterns are close each other, but we are not sure they are overriding... Let's do the classic job...
            throw new NotImplementedException("I'm bored, don't want to browse the net to find the needed equations..." );
        }
    }
 
    class Circle : Pattern
    {
        public Point Center;
        public int Radius;
 
        public Circle(Point center, int radius)
        {
            this.Center = center;
            this.Radius = radius;
 
            this.BoundingBox1 = new Point(center.X - radius, center.Y - radius);
            this.BoundingBox2 = new Point(center.X + radius, center.Y + radius);
        }
    }
 
    class Quadrilateral : Pattern
    {
        public Point PointA;
        public Point PointB;
        public Point PointC;
        public Point PointD;
 
        public Quadrilateral(Point pointA, Point pointB, Point pointC, Point pointD)
        {
            this.PointA = pointA;
            this.PointB = pointB;
            this.PointC = pointC;
            this.PointD = pointD;
 
            this.BoundingBox1 = new Point(Math.Min(Math.Min(pointA.X, pointB.X), Math.Min(pointC.X, pointD.X)), Math.Min(Math.Min(pointA.Y, pointB.Y), Math.Min(pointC.Y, pointD.Y)));
            this.BoundingBox2 = new Point(Math.Max(Math.Max(pointA.X, pointB.X), Math.Max(pointC.X, pointD.X)), Math.Max(Math.Max(pointA.Y, pointB.Y), Math.Max(pointC.Y, pointD.Y)));
        }
    }
}

// Step 1 : Check bounding boxes (optim1)
            if (optim1)
            {
                if (
                    // Case 1 : this pattern hasn't a top of it's bounding box inside the other one's
                    !MathTools.PointInRectangle(this.BoundingBox1, otherPattern.BoundingBox1, otherPattern.BoundingBox2) && !MathTools.PointInRectangle(this.BoundingBox2, otherPattern.BoundingBox1, otherPattern.BoundingBox2) &&
                    // Case 2 : the other pattern hasn't a top of it's bounding box inside this one's
                    !MathTools.PointInRectangle(otherPattern.BoundingBox1, this.BoundingBox1, this.BoundingBox2) && !MathTools.PointInRectangle(otherPattern.BoundingBox2, this.BoundingBox1, this.BoundingBox2) &&
                    // Case 3 : the other pattern bounding box isn't crossing this one's (horizontal)
                    !(otherPattern.BoundingBox1.X <= this.BoundingBox1.X && otherPattern.BoundingBox2.X >= this.BoundingBox2.X && otherPattern.BoundingBox1.Y >= this.BoundingBox1.Y && otherPattern.BoundingBox1.Y <= this.BoundingBox2.Y) &&
                    // Case 4 : the other pattern bounding box isn't crossing the other one's
                    !(otherPattern.BoundingBox1.X >= this.BoundingBox1.X && otherPattern.BoundingBox1.X <= this.BoundingBox2.X && otherPattern.BoundingBox1.Y <= this.BoundingBox1.Y && otherPattern.BoundingBox2.Y >= this.BoundingBox1.Y)
                )
                {
                    // Bounding boxes are not overriding
                    return false;
                }
            }