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

namespace TSP
{
    public class EdgeStruct : IComparable
    {
        private int cityIndexL, cityIndexR;
        private double cityDistance;
        private Object edgeValues;          // For additional edge labelling

        public EdgeStruct(City cl, City cr)
        {
            cityIndexL = cl.Index;
            cityIndexR = cr.Index;
            cityDistance = Math.Sqrt((cl.X - cr.X) * (cl.X - cr.X) + (cl.Y - cr.Y) * (cl.Y - cr.Y));
        }

        public int CompareTo(object obj)
        {
            EdgeStruct e = (EdgeStruct)obj;

            if (e.cityDistance < cityDistance)
                return 1;
            else if (e.cityDistance > cityDistance)
                return -1;
            else
                return 0;
        }

        public int LeftCity
        {
            get { return cityIndexL; }
        }

        public int RightCity
        {
            get { return cityIndexR; }
        }

        public double CityDistance
        {
            get { return cityDistance; }
        }

        public Object EdgeValues
        {
            get { return edgeValues; }

            set { edgeValues = value; }
        }

        public override string ToString()
        {
            Console.WriteLine("City indexes " + cityIndexL + " " + cityIndexR);
            Console.WriteLine("Distance " + cityDistance);
            return null;
        }
    }

    public class City
    {
        private int index;
        private Boolean visited;
        private double x;
        private double y;

        public City(int _i, double _x, double _y)
        {
            index = _i; x = _x; y = _y; visited = false;
        }

        public int Index
        {
            get { return index; }
        }

        public double X
        {
            get { return x; }

            set { x = value; }
        }

        public double Y
        {
            get { return y; }

            set { y = value; }
        }

        public Boolean Visited
        {
            get { return visited; }

            set { visited = value; }
        }
    }


    public class TSPGrid
    {
        private EdgeStruct[][] adjacencyArray;

        private City[] cities;

        private int gridSize;
       
        public TSPGrid(double[,] data, int size)
        {
            gridSize = size;
            adjacencyArray = new EdgeStruct[gridSize][];

            cities = new City[gridSize];

            for (int i = 0; i < gridSize; i++)
            {
                cities[i] = new City(i, data[i, 0], data[i, 1]);
                adjacencyArray[i] = new EdgeStruct[gridSize-1];
            }

            for (int i = 0; i < gridSize; i++)
            {
                int count = 0;
                for (int j = 0; j < gridSize; j++)
                {
                    if (i!=j)
                        adjacencyArray[i][count++] = new EdgeStruct(cities[i], cities[j]);
                }

                // Sort each row of the adjacency array in order of edge distance
                Array.Sort<EdgeStruct>(adjacencyArray[i]);
            }

        }

        public int GridSize
        {
            get { return gridSize; }
        }

        public EdgeStruct[][] AdjacencyArray
        {
            get { return adjacencyArray; }
        }

        public override string ToString()
        {
            for (int i = 0; i < 2; i++)
            {
                Console.WriteLine("City index " + i);
                for (int j = 0; j < gridSize-1; j++)
                {
                    Console.WriteLine(AdjacencyArray[i][j] + "\n");
                }
            }

            return null;
        }

        public City[] Cities
        {
            get { return cities; }
        }

    }

    class TSPMain
    {
        static void Main(string[] args)
        {
            double[,] data = {{20833.3333,17100.0000},{20900.0000,17066.6667}, {21300.0000,13016.6667},
            {21600.0000,14150.0000}, {21600.0000,14966.6667}, {21600.0000,16500.0000}, {22183.3333,13133.3333},
            {22583.3333,14300.0000},{22683.3333,12716.6667}, {23616.6667,15866.6667}, {23700.0000,15933.3333},
            {23883.3333,14533.3333}, {24166.6667,13250.0000}, {25149.1667,12365.8333}, {26133.3333,14500.0000},
            {26150.0000,10550.0000}, {26283.3333,12766.6667}, {26433.3333,13433.3333}, {26550.0000,13850.0000},
            {26733.3333,11683.3333}, {27026.1111,13051.9444}, {27096.1111,13415.8333}, {27153.6111,13203.3333},
            {27166.6667,9833.3333}, {27233.3333,10450.0000}, {27233.3333,11783.3333}, {27266.6667,10383.3333},
            {27433.3333,12400.0000}, {27462.5000,12992.2222}};


            int size = data.Length / 2;

            TSPGrid grid = new TSPGrid(data, size);

            Console.WriteLine(grid);
        }
    }
}