第6回PAST L 都市計画

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("2 1");
            WillReturn.Add("0 0");
            WillReturn.Add("6 0");
            WillReturn.Add("3 0 2");
            //2.00000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add("4 2");
            WillReturn.Add("0 1");
            WillReturn.Add("0 0 2");
            WillReturn.Add("0 1 4");
            //2.12310562562
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3 4");
            WillReturn.Add("9 2");
            WillReturn.Add("5 20");
            WillReturn.Add("0 21");
            WillReturn.Add("0 0 2");
            WillReturn.Add("0 0 10");
            WillReturn.Add("16 0 10");
            WillReturn.Add("10 15 3");
            //13.10603728957
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NodeInfoDef
    {
        internal bool IsCircle;
        internal double X;
        internal double Y;
        internal double R;
    }
    static List<NodeInfoDef> mNodeInfoList = new List<NodeInfoDef>();

    // 円の添え字のList
    static List<int> mCircleIndList = new List<int>();

    // 無向グラフの辺の情報
    struct EdgeInfoDef
    {
        internal int FromNode;
        internal int ToNode;
        internal double Cost;
    }
    static List<EdgeInfoDef> mEdgeInfoList = new List<EdgeInfoDef>();

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

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

        SplitAct(InputList[0]);
        int N = wkArr[0];

        foreach (string EachStr in InputList.Skip(1).Take(N)) {
            SplitAct(EachStr);
            NodeInfoDef WillAdd;
            WillAdd.IsCircle = false;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.R = 0;
            mNodeInfoList.Add(WillAdd);
        }

        foreach (string EachStr in InputList.Skip(1 + N)) {
            SplitAct(EachStr);
            NodeInfoDef WillAdd;
            WillAdd.IsCircle = true;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            WillAdd.R = wkArr[2];
            mNodeInfoList.Add(WillAdd);
        }

        // 円の添え字のList
        for (int I = 0; I <= mNodeInfoList.Count - 1; I++) {
            if (mNodeInfoList[I].IsCircle) {
                mCircleIndList.Add(I);
            }
        }

        List<HashSet<int>> NonUseCircleSetList = DeriveNonUseCircleSetList();

        for (int I = 0; I <= mNodeInfoList.Count - 1; I++) {
            for (int J = I + 1; J <= mNodeInfoList.Count - 1; J++) {
                EdgeInfoDef WillAdd;
                WillAdd.FromNode = I;
                WillAdd.ToNode = J;

                bool IsCircle1 = mNodeInfoList[I].IsCircle;
                bool IsCircle2 = mNodeInfoList[J].IsCircle;
                if (IsCircle1 == false && IsCircle2 == false) {
                    PointDef Point1;
                    Point1.X = mNodeInfoList[I].X;
                    Point1.Y = mNodeInfoList[I].Y;

                    PointDef Point2;
                    Point2.X = mNodeInfoList[J].X;
                    Point2.Y = mNodeInfoList[J].Y;

                    WillAdd.Cost = DeriveDistance1(Point1, Point2);
                }
                else if (IsCircle1 == false && IsCircle2) {
                    PointDef Point1;
                    Point1.X = mNodeInfoList[I].X;
                    Point1.Y = mNodeInfoList[I].Y;

                    CircleInfoDef Circle1;
                    Circle1.X = mNodeInfoList[J].X;
                    Circle1.Y = mNodeInfoList[J].Y;
                    Circle1.R = mNodeInfoList[J].R;

                    WillAdd.Cost = DeriveDistance2(Point1, Circle1);
                }
                else if (IsCircle1 && IsCircle2 == false) {
                    CircleInfoDef Circle1;
                    Circle1.X = mNodeInfoList[I].X;
                    Circle1.Y = mNodeInfoList[I].Y;
                    Circle1.R = mNodeInfoList[I].R;

                    PointDef Point1;
                    Point1.X = mNodeInfoList[J].X;
                    Point1.Y = mNodeInfoList[J].Y;

                    WillAdd.Cost = DeriveDistance2(Point1, Circle1);
                }
                else {
                    CircleInfoDef Circle1;
                    Circle1.X = mNodeInfoList[I].X;
                    Circle1.Y = mNodeInfoList[I].Y;
                    Circle1.R = mNodeInfoList[I].R;

                    CircleInfoDef Circle2;
                    Circle2.X = mNodeInfoList[J].X;
                    Circle2.Y = mNodeInfoList[J].Y;
                    Circle2.R = mNodeInfoList[J].R;

                    WillAdd.Cost = DeriveDistance3(Circle1, Circle2);
                }
                mEdgeInfoList.Add(WillAdd);
            }
        }
        // 枝をコストの昇順にソート
        mEdgeInfoList.Sort((a, b) => a.Cost.CompareTo(b.Cost));

        double Answer = double.MaxValue;
        foreach (HashSet<int> EachNonUseCircleSet in NonUseCircleSetList) {
            double AnswerKouho = DeriveMST(EachNonUseCircleSet);
            Answer = Math.Min(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }

    // 使用する小さな塔のIndSetを引数として、MSTのコストを返す
    static double DeriveMST(HashSet<int> pNonUseCircleSet)
    {
        // クラスカル法で解く
        var InsUnionFind = new UnionFind();
        for (int I = 0; I <= mNodeInfoList.Count - 1; I++) {
            if (pNonUseCircleSet.Contains(I)) continue;

            InsUnionFind.MakeSet(I);
        }

        double SumCost = 0;
        foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoList) {
            if (pNonUseCircleSet.Contains(EachEdgeInfo.FromNode)) continue;
            if (pNonUseCircleSet.Contains(EachEdgeInfo.ToNode)) continue;

            int FromNode = EachEdgeInfo.FromNode;
            int ToNode = EachEdgeInfo.ToNode;
            int RootNode1 = InsUnionFind.FindSet(EachEdgeInfo.FromNode);
            int RootNode2 = InsUnionFind.FindSet(EachEdgeInfo.ToNode);
            if (RootNode1 != RootNode2) {
                InsUnionFind.Unite(FromNode, ToNode);
                SumCost += EachEdgeInfo.Cost;
            }
        }
        return SumCost;
    }

    struct JyoutaiDef
    {
        internal int CurrInd;
        internal HashSet<int> CircleIndSet;
    }

    // DFSで、未使用の円を列挙
    static List<HashSet<int>> DeriveNonUseCircleSetList()
    {
        var NonUseCircleSetList = new List<HashSet<int>>();

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrInd = 0;
        WillPush.CircleIndSet = new HashSet<int>();
        Stk.Push(WillPush);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            NonUseCircleSetList.Add(Popped.CircleIndSet);

            for (int I = Popped.CurrInd; I <= mCircleIndList.Count - 1; I++) {
                WillPush.CurrInd = I + 1;
                WillPush.CircleIndSet = new HashSet<int>(Popped.CircleIndSet);
                WillPush.CircleIndSet.Add(mCircleIndList[I]);
                Stk.Push(WillPush);
            }
        }
        return NonUseCircleSetList;
    }

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

    struct CircleInfoDef
    {
        internal double X;
        internal double Y;
        internal double R;
    }

    // 円と円の位置関係を判定する
    // 判定1 一方の円が他方の円を完全に含み、2つの円は接していない
    // 判定2 一方の円が他方の円を完全に含み、2つの円は接している
    // 判定3 2つの円が互いに交差する
    // 判定4 2つの円の内部に共通部分は存在しないが、2つの円は接している
    // 判定5 2つの円の内部に共通部分は存在せず、2つの円は接していない
    static int CheckTwoCircle(CircleInfoDef pCircleInfo1, CircleInfoDef pCircleInfo2)
    {
        PointDef DiffVect = SetVector(pCircleInfo1.X, pCircleInfo1.Y,
                                      pCircleInfo2.X, pCircleInfo2.Y);
        double DiffVectNorm = DeriveNorm(DiffVect);

        double RDiff = pCircleInfo1.R - pCircleInfo2.R;
        double RDiffNorm = RDiff * RDiff;

        double RSum = pCircleInfo1.R + pCircleInfo2.R;
        double RSumNorm = RSum * RSum;

        // 判定1
        if (DiffVectNorm < RDiffNorm) {
            return 1;
        }

        // 判定2
        if (DiffVectNorm == RDiffNorm) {
            return 2;
        }

        // 判定3
        if (RDiffNorm < DiffVectNorm && DiffVectNorm < RSumNorm) {
            return 3;
        }

        // 判定4
        if (RSumNorm == DiffVectNorm) {
            return 4;
        }

        // 判定5
        return 5;
    }

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

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

    // 点と点との距離を返す
    static double DeriveDistance1(PointDef pPoint1, PointDef pPoint2)
    {
        double XDiff = pPoint1.X - pPoint2.X;
        double YDiff = pPoint1.Y - pPoint2.Y;
        return Math.Sqrt(XDiff * XDiff + YDiff * YDiff);
    }

    // 点と円との距離を返す
    static double DeriveDistance2(PointDef pPoint1, CircleInfoDef pCircleInfo1)
    {
        double XDiff = pPoint1.X - pCircleInfo1.X;
        double YDiff = pPoint1.Y - pCircleInfo1.Y;
        double Distance = Math.Sqrt(XDiff * XDiff + YDiff * YDiff);
        return Math.Abs(Distance - pCircleInfo1.R);
    }

    // 円と円との距離を返す
    static double DeriveDistance3(CircleInfoDef pCircleInfo1, CircleInfoDef pCircleInfo2)
    {
        int ChechResult = CheckTwoCircle(pCircleInfo1, pCircleInfo2);
        if (ChechResult == 2 || ChechResult == 3 || ChechResult == 4) {
            return 0;
        }

        // 円の中心同士の距離を求める
        double XDiff = pCircleInfo1.X - pCircleInfo2.X;
        double YDiff = pCircleInfo1.Y - pCircleInfo2.Y;
        double Distance = Math.Sqrt(XDiff * XDiff + YDiff * YDiff);

        // 円1を原点とし、数直線で考える
        var PosList1 = new List<double>();
        PosList1.Add(0 + pCircleInfo1.R);
        PosList1.Add(0 - pCircleInfo1.R);

        var PosList2 = new List<double>();
        PosList2.Add(Distance + pCircleInfo2.R);
        PosList2.Add(Distance - pCircleInfo2.R);

        // 2*2の4通りの組み合わせを全て試す
        var AnswerList = new List<double>();
        foreach (double EachPos1 in PosList1) {
            foreach (double EachPos2 in PosList2) {
                AnswerList.Add(Math.Abs(EachPos1 - EachPos2));
            }
        }
        return AnswerList.Min();
    }
}

// UnionFindクラス
internal class UnionFind
{
    private class NodeInfoDef
    {
        internal int ParentNode;
        internal int Rank;
    }
    private Dictionary<int, NodeInfoDef> mNodeInfoDict =
        new Dictionary<int, NodeInfoDef>();

    // 要素が1つである木を森に追加
    internal void MakeSet(int pNode)
    {
        NodeInfoDef WillAdd = new NodeInfoDef();
        WillAdd.ParentNode = pNode;
        WillAdd.Rank = 0;
        mNodeInfoDict[pNode] = WillAdd;
    }

    // 合併処理
    internal void Unite(int pX, int pY)
    {
        int XNode = FindSet(pX);
        int YNode = FindSet(pY);
        int XRank = mNodeInfoDict[XNode].Rank;
        int YRank = mNodeInfoDict[YNode].Rank;

        if (XRank > YRank) {
            mNodeInfoDict[YNode].ParentNode = XNode;
        }
        else {
            mNodeInfoDict[XNode].ParentNode = YNode;
            if (XRank == YRank) {
                mNodeInfoDict[YNode].Rank++;
            }
        }
    }

    // ノードを引数として、木の根を取得
    internal int FindSet(int pTargetNode)
    {
        // 根までの経路上のノードのList
        var PathNodeList = new List<int>();

        int CurrNode = pTargetNode;
        while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
            PathNodeList.Add(CurrNode);
            CurrNode = mNodeInfoDict[CurrNode].ParentNode;
        }

        // 経路圧縮 (親ポインタの付け替え)
        foreach (int EachPathNode in PathNodeList) {
            NodeInfoDef wkNodeInfo = mNodeInfoDict[EachPathNode];
            wkNodeInfo.ParentNode = CurrNode;
            mNodeInfoDict[EachPathNode] = wkNodeInfo;
        }
        return CurrNode;
    }

    internal void DebugPrint()
    {
        foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
            Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
                EachPair.Key, EachPair.Value.ParentNode);
        }
    }
}

解説

最小シュタイナー木問題ですので、
環境交差点の使用有無を全探索してます。

類題

第1回PAST L グラデーション