using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using System.Drawing;
using System.Drawing.Drawing2D;

namespace ProgrammingChallenges
{
   class Program
   {
      private const float RADIANS_TO_DEGREES = (float)(180 / Math.PI);

      public static bool PolygonIsSymmetrical(List<PointF> vertices)
      {
         // The algorithm:
         // 1. Find potential lines of symmetry.  For odd-sided polygons, these lines go from each
         //    vertex to the midpoint of the opposite line.  For even-sided polygons, these lines 
         //    go from each vertex to the opposite vertex, and from each line's midpoint to the 
         //    opposite line's midpoint.
         //
         // 2. For each potential line of symmetry, see if the vertices on one side of the line
         //    mirror the vertices on the other side.  If this is the case for any line, the 
         //    polygon is symmetrical.  This algorithm tests this by rotating and translating the
         //    polygon so that the potential line of symmetry is vertical and lies on the y axis.
         //    Then two vertices are symmetric if they have the same Y value and opposite X value.

         if (vertices.Count % 2 == 1) // odd number of vertices
         {
            for (int i = 0; i < vertices.Count; i++)
            {
               int startIndex1 = i;
               int startIndex2 = (i + 1) % vertices.Count;
               PointF divideStart = Midpoint(vertices[startIndex1], vertices[startIndex2]);
               PointF divideEnd = vertices[(startIndex2 + vertices.Count / 2) % vertices.Count];
               if (IsLineOfSymmetry(divideStart, divideEnd, vertices, startIndex1, startIndex2,
                   vertices.Count / 2))
               {
                  return true;
               }
            }
            return false;
         }
         else // even number of vertices
         {
            for (int i = 0; i < vertices.Count / 2; i++)
            {
               int startIndex1 = Modulo(i - 1, vertices.Count);
               int startIndex2 = i + 1;
               PointF oppositeVertex1 = vertices[(i + vertices.Count / 2) % vertices.Count];
               PointF oppositeVertex2 = vertices[(i + vertices.Count / 2 + 1) % vertices.Count];
               // Look for lines of symmetry from vertex to opposite vertex
               // and from midpoint to opposite midpoint
               if (IsLineOfSymmetry(vertices[i], oppositeVertex1, vertices,
                                   startIndex1, startIndex2, vertices.Count / 2 - 1) ||
                   IsLineOfSymmetry(Midpoint(vertices[i], vertices[startIndex2]),
                                    Midpoint(oppositeVertex1, oppositeVertex2),
                                    vertices, i, startIndex2, vertices.Count / 2))
               {
                  return true;
               }
            }
            return false;
         }
      }

      /// <summary>
      /// Determines whethere a line going from divideStart to divideEnd is a line of symmetry for
      /// a polygon with the given vertices. Compares the vertex at startIndex1 to the vertex at
      /// startIndex2, then decrements startIndex1 and increments startIndex2, and returns false
      /// if they aren't symmetrical.  This is done numComparisons times.
      /// </summary>
      /// <param name="divideStart">The start of the dividing line.</param>
      /// <param name="divideEnd">The end of the dividing line.</param>
      /// <param name="vertices">The vertices of the polygon that the line is dividing.</param>
      /// <param name="startIndex1">The index of first vertex to compare.</param>
      /// <param name="startIndex2">The index of the vertex to compare to the first vertex.</param>
      /// <param name="numComparisons">The number of pairs of vertices to compare.</param>
      /// <returns>True if the line is a line of symmetry, false otherwise.</returns>
      private static bool IsLineOfSymmetry(PointF divideStart, PointF divideEnd, List<PointF> vertices,
                                       int startIndex1, int startIndex2, int numComparisons)
      {
         // Translate and rotate the polygon so divideStart is at the origin
         // and the dividing line is vertical.         
         Matrix transform = new Matrix();
         double rotateAmount = Angle(divideStart, divideEnd) * -1 + 90;
         PointF[] vertexArray = vertices.ToArray();
         transform.Translate(-divideStart.X, -divideStart.Y);
         transform.Rotate(Angle(divideStart, divideEnd) * -1 + 90);
         transform.TransformPoints(vertexArray);

         for (int i = 0; i < numComparisons; i++)
         {
            // If any compared point doesn't have a corresponding point with the opposite
            // X value and same Y value, the line is not a line of symmetry.
            PointF vertex1 = vertexArray[Modulo(startIndex1 - i, vertexArray.Count())];
            PointF vertex2 = vertexArray[Modulo(startIndex2 + i, vertexArray.Count())];
            if (vertex1.X != -vertex2.X || vertex1.Y != vertex2.Y)
            {
               return false;
            }
         }
         return true;
      }

      /// <summary>
      /// Calculates angle in degrees between line defined with two points and the x axis.
      /// </summary>
      private static float Angle(PointF start, PointF end)
      {
         return (float)(Math.Atan2(end.Y - start.Y, end.X - start.X) * RADIANS_TO_DEGREES);
      }

      /// <summary>
      /// A modulo function that works with negative values of x.
      /// </summary>
      private static int Modulo(int x, int modBy)
      {
         return (x % modBy + modBy) % modBy;
      }

      private static PointF Midpoint(PointF point1, PointF point2)
      {
         return new PointF((point1.X + point2.X) / 2, (point1.Y + point2.Y) / 2);
      }

      public static void TestPolygonIsSymmetrical(string name, bool expectedResult,
                                                  params PointF [] vertices)
      {
         Console.WriteLine( string.Format("Running test {0}" + Environment.NewLine 
                                          + "  Expected result: {1}", name, expectedResult));
         bool actualResult = PolygonIsSymmetrical(vertices.ToList());
         Console.WriteLine(expectedResult == actualResult ? "  Success!" : "  Failure!");
      }

      static void Main(string[] args)
      {
         // Output:
         // Running test Square
         //   Expected result: true
         //   Success!
         // Running test Rectangle
         //   Expected result: true
         //   Success!
         // Running test Rhombus
         //   Expected result: true
         //   Success!
         // Running test Pentagon
         //   Expected result: true
         //   Success!
         // Running test Asymmetrical Pentagon
         //   Expected result: false
         //   Success!
         // Running test Asymmetrical Hexagon
         //   Expected result: false
         //   Success!

         TestPolygonIsSymmetrical("Square", 
                                  true,
                                  new PointF(-3, -3),
                                  new PointF(3, -3),
                                  new PointF(3, 3),
                                  new PointF(-3, 3));
         TestPolygonIsSymmetrical("Rectangle",
                                  true,
                                  new PointF(2, 2),
                                  new PointF(8, 2), 
                                  new PointF(8, 7),
                                  new PointF(2, 7));
         TestPolygonIsSymmetrical("Rhombus",
                                  true,
                                  new PointF(-4, 0),
                                  new PointF(0, 3),
                                  new PointF(4, 0),
                                  new PointF(0, -3));
         TestPolygonIsSymmetrical("Pentagon",
                                  true,
                                  new PointF(0, 2),
                                  new PointF(5, 2),
                                  new PointF(6, 6),
                                  new PointF(2.5f, 10),
                                  new PointF(-1, 6));
         TestPolygonIsSymmetrical("Asymmetrical Pentagon",
                                  false,
                                  new PointF(0, 2),
                                  new PointF(6, 2),
                                  new PointF(6, 6),
                                  new PointF(2.5f, 10),
                                  new PointF(-1, 6));
         TestPolygonIsSymmetrical("Asymmetrical Hexagon",
                                  false,
                                  new PointF(0, 2),
                                  new PointF(6, 2),
                                  new PointF(6, 6),
                                  new PointF(5, 9),
                                  new PointF(2.5f, 10),
                                  new PointF(-1, 6));
         Console.Read();
      }
   }
}