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

namespace Gramahm2
{
    class Program
    {
        static void Main(string[] args)
        {
            //var points = new List<Point>
            //{
            //    new Point { X=1.9, Y=4.3,   Name="A" },
            //    new Point { X=2.1, Y=8.4,   Name="B" },
            //    new Point { X=2.8, Y=5.3,   Name="C" },
            //    new Point { X=3.2, Y=10.7,  Name="D" },
            //    new Point { X=3.3, Y=3.1,   Name="E" },
            //    new Point { X=8.5, Y=9.9,   Name="F" },
            //    new Point { X=6, Y=3,     Name="G" },
            //    new Point { X=0.1, Y=0.1,   Name="H" },
            //};

           //Bugged
           var points = new List<Point>
           {
                new Point { X=1, Y=1,   Name="A" },
                new Point { X=3, Y=1,   Name="B" },
                new Point { X=5, Y=1,   Name="C" },
                new Point { X=7, Y=1,  Name="D" },
                new Point { X=7, Y=3,   Name="E" },
                new Point { X=7, Y=5,   Name="F" },
                new Point { X=7, Y=7,     Name="G" },
                new Point { X=5, Y=5,   Name="H" },
                new Point { X=3, Y=3,   Name="I" },
           };

            var p0value = points.Min(p => p.Y);
            var p0 = points.First(p => p.Y == p0value);

            Console.WriteLine("P0:");
            Console.WriteLine(p0);
            Console.WriteLine();

            var sortedByAngle = points.OrderBy(p => Math.Atan2(p.Y - p0.Y, p.X - p0.X));

            Console.WriteLine("Sorted by angle:");
            foreach (var p in sortedByAngle)
                Console.WriteLine(p);
            Console.WriteLine();

            foreach (var p in sortedByAngle)
                p.distanceFromP0 = p.Distance(p0);

            for(var i = 0; i < sortedByAngle.Count()-1; i++)
            {
                var next = sortedByAngle.ElementAt(i + 1);

                if (next == sortedByAngle.ElementAt(sortedByAngle.Count() - 1))
                    continue;

                if(sortedByAngle.ElementAt(i).)
            }

            /*
	// remove duplicate angles'
	for (auto& p : sorted_by_angle)
		p->distance_from_p0 = p->distance(p0);


	for (auto it = sorted_by_angle.begin(); it != sorted_by_angle.end(); it++)
	{
		auto next = std::next(it);
		if (next == sorted_by_angle.end())
			continue;

		if ((*it)->angle != (*next)->angle)
			continue;

		auto duplication_end = next;
		while (next != sorted_by_angle.end() && (*next)->angle == (*it)->angle)
			duplication_end = next++;

		std::sort(it, duplication_end+1, by_distance(p0));

		it = duplication_end;
	}

	auto it = sorted_by_angle.begin();
	while (it != sorted_by_angle.end())
	{
		if ((it + 1) == sorted_by_angle.end())
			break;

		if ((*it)->angle == (*(it+1))->angle)
		{
			sorted_by_angle.erase(it + 1);
		}
		else ++it;
	}

	//std::sort(sorted_by_angle.begin(), sorted_by_angle.end(), by_distance(p0));

	printf("Sorted by angle w/o duplicates:\n");
	for (auto& p : sorted_by_angle)
		p->print();

            */

            Stack<Point> output = new Stack<Point>();
            output.Push(sortedByAngle.ElementAt(0));
            output.Push(sortedByAngle.ElementAt(1));
            output.Push(sortedByAngle.ElementAt(2));

            for (int i = 3; i < sortedByAngle.Count(); i++)
            {
                Point top = output.Peek();
                output.Pop();

                while (output.Count() > 0 && Point.Sign(output.Peek(), top, sortedByAngle.ElementAt(i)) <= 0)
                {
                    top = output.Peek();
                    output.Pop();
                }

                output.Push(top);
                output.Push(sortedByAngle.ElementAt(i));
            }

            output.Push(p0);

            Console.WriteLine("Otoczka:");
            foreach (var p in output)
                Console.WriteLine(p);

            Console.ReadKey();
        }
    }
}