【C#】怪盗paizaからの挑戦状の解答

paiza.jp
解答のせていいとのことなので。
最短経路じゃないです。
なんか有名なアルゴリズムとか使うのかな？
Tupleが使えて満足。

using System;
using System.Collections.Generic;
   class Program
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine();
            int N = int.Parse(line);

            var xyList = new List<Tuple<double, double>>();
            //座標リストの入力と生成
            for (int i = 0; i < N; i++)
            {
                var data = Console.ReadLine().Split(' ');
                double x = double.Parse(data[0]);
                double y = double.Parse(data[1]);
                xyList.Add(Tuple.Create(x, y));
            }
            

            var originPoint = Tuple.Create(0.0, 0.0);
            var minRoot = new List<Tuple<double, double>>();
            minRoot.Add(originPoint);
            var minPoint = originPoint;

            while (xyList.Count > 0)
            {
                double minDist2point = double.MaxValue;
                var tempMinPoint = Tuple.Create(0.0, 0.0);
                //現在の点からの最短距離点算出
                foreach (var point in xyList)
                {
                    var tempMinDist = TwoPointDistance(minPoint, point);
                    if (tempMinDist < minDist2point)
                    {
                        tempMinPoint = point;
                        minDist2point = tempMinDist;
                    }
                }
                //決定した最短距離ポイントを除外
                xyList.Remove(tempMinPoint);

                //現在の点更新
                minPoint = tempMinPoint;

                //ルート更新
                minRoot.Add(minPoint);
            }

            minRoot.Remove(originPoint);
            minRoot.ForEach(s => Console.WriteLine(s.Item1+" "+s.Item2));

        }
        //2点間の距離公式
        static double TwoPointDistance(Tuple<double, double> t1, Tuple<double, double> t2)
        {
            return Math.Sqrt(Math.Pow(t2.Item1 - t1.Item1, 2.0) + Math.Pow(t2.Item2 - t1.Item2, 2.0));
        }
        
    }

・結果
paiza.jp

・説明
始点Oからスタートして全ポイントの距離の中で距離が最短になるポイントPを選ぶ
→PからOとP以外の全ポイントの距離の中で距離が最短になるポイントP2を選ぶ
→以下繰り返し

一番近い地点を次々結んでいくだけなので、「遠回りっぽいけど全体としては近い」みたいなルートだと最短にならないと思われ。