CGL_4_A: Convex Hull

問題へのリンク

C#のソース

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

// Q068 凸包 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7");
            WillReturn.Add("2 1");
            WillReturn.Add("0 0");
            WillReturn.Add("1 2");
            WillReturn.Add("2 2");
            WillReturn.Add("4 2");
            WillReturn.Add("1 3");
            WillReturn.Add("3 3");
            //5
            //0 0
            //2 1
            //4 2
            //3 3
            //1 3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 0");
            WillReturn.Add("1 0");
            WillReturn.Add("-1 2");
            //3
            //0 0
            //1 0
            //-1 2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct PointDef
    {
        internal double X;
        internal double Y;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        double[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => double.Parse(X)).ToArray();

        var XYInfoList = new List<PointDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            XYInfoList.Add(WillAdd);
        }

        List<PointDef> AndrewScanResult = AndrewScan(XYInfoList);
        Console.WriteLine(AndrewScanResult.Count);

        var Query = AndrewScanResult.OrderBy(pX => pX.Y).ThenBy(pX => pX.X).First();
        int StaInd = AndrewScanResult.FindIndex(pX => pX.X == Query.X && pX.Y == Query.Y);
        int UB = AndrewScanResult.Count - 1;
        for (int I = StaInd; I <= UB; I++) {
            Console.WriteLine("{0} {1}", AndrewScanResult[I].X, AndrewScanResult[I].Y);
        }
        for (int I = 0; I < StaInd; I++) {
            Console.WriteLine("{0} {1}", AndrewScanResult[I].X, AndrewScanResult[I].Y);
        }
    }

    // アンドリューのアルゴリズムで凸包の座標のListを返す
    static List<PointDef> AndrewScan(List<PointDef> pPointList)
    {
        if (pPointList.Count < 3) return pPointList;

        // X,Yを基準にソート
        PointDef[] SortedPointArr = pPointList.OrderBy(pX => pX.X).ThenBy(pX => pX.Y).ToArray();

        int UB = SortedPointArr.GetUpperBound(0);

        // 凸包の上部の座標のList
        var UpperList = new List<PointDef>();

        // Xが小さいのものから2つを追加
        UpperList.Add(SortedPointArr[0]);
        UpperList.Add(SortedPointArr[1]);

        // 凸包の下部の座標のList
        var LowerList = new List<PointDef>();

        // Xが大きいのものから2つを追加
        LowerList.Add(SortedPointArr[UB]);
        LowerList.Add(SortedPointArr[UB - 1]);

        // 凸包の上部を生成
        for (int I = 2; I <= UB; I++) {
            for (int J = UpperList.Count; 2 <= J; J--) {
                if (CCW(UpperList[J - 2], UpperList[J - 1], SortedPointArr[I]) == 1) {
                    UpperList.RemoveAt(UpperList.Count - 1);
                }
                else {
                    break;
                }
            }
            UpperList.Add(SortedPointArr[I]);
        }

        // 凸包の下部を生成
        for (int I = UB - 2; 0 <= I; I--) {
            for (int J = LowerList.Count; 2 <= J; J--) {
                if (CCW(LowerList[J - 2], LowerList[J - 1], SortedPointArr[I]) == 1) {
                    LowerList.RemoveAt(LowerList.Count - 1);
                }
                else {
                    break;
                }
            }
            LowerList.Add(SortedPointArr[I]);
        }

        // 凸法の点の列を生成
        LowerList.Reverse();
        for (int I = UpperList.Count - 2; 1 <= I; I--) {
            LowerList.Add(UpperList[I]);
        }

        return LowerList;
    }

    static int CCW(PointDef pPointA, PointDef pPointB, PointDef pPointC)
    {
        const int COUNTER_CLOCKWISE = 1;
        const int CLOCKWISE = -1;
        const int ONLINE_BACK = 2;
        const int ONLINE_FRONT = -2;
        const int ON_SEGMENT = 0;

        PointDef VectorA = SetVector(pPointA, pPointB);
        PointDef VectorB = SetVector(pPointA, pPointC);

        // 外積 A*Bを求める
        double Cross = DeriveCross(VectorA, VectorB);

        // Aの半時計回りの方向にBが存在する
        if (Cross > 0) {
            return COUNTER_CLOCKWISE;
        }

        // Aの時計回りの方向にBが存在する
        if (Cross < 0) {
            return CLOCKWISE;
        }

        // 3点が1直線にある場合

        // 内積がマイナスなら、ベクトルの向きは反対
        double Dot = DeriveDot(VectorA, VectorB);
        if (Dot < 0) {
            return ONLINE_BACK;
        }

        double NormA = DeriveNorm(VectorA);
        double NormB = DeriveNorm(VectorB);
        if (NormA < NormB) {
            return ONLINE_FRONT;
        }
        return ON_SEGMENT;
    }

    // 始点と終点の座標を引数として、始点から終点へのベクトルを返す
    static PointDef SetVector(PointDef pStaPoint, PointDef pEndPoint)
    {
        PointDef WillReturn;
        WillReturn.X = pEndPoint.X - pStaPoint.X;
        WillReturn.Y = pEndPoint.Y - pStaPoint.Y;
        return WillReturn;
    }

    // 内積を求める
    static double DeriveDot(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.X + pVector1.Y * pVector2.Y;
    }

    // 外積を求める
    static double DeriveCross(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.Y - pVector1.Y * pVector2.X;
    }

    // ベクトルの大きさを求める
    static double DeriveABS(PointDef pVector)
    {
        double wkNorm = DeriveNorm(pVector);
        double wkSqrt = Math.Sqrt(wkNorm);
        return wkSqrt;
    }

    // ベクトルのNormを求める
    static double DeriveNorm(PointDef pVector)
    {
        return pVector.X * pVector.X + pVector.Y * pVector.Y;
    }
}

解説

アンドリューのアルゴリズムを使ってます。