DSL_4_A: Union of Rectangles

問題へのリンク

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");
            WillReturn.Add("0 0 3 4");
            WillReturn.Add("1 2 4 3");
            //13
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("1 1 2 5");
            WillReturn.Add("2 1 5 2");
            WillReturn.Add("1 2 2 5");
            //7
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            WillReturn.Add("0 0 3 1");
            WillReturn.Add("0 0 1 3");
            WillReturn.Add("0 2 3 3");
            WillReturn.Add("2 0 3 3");
            //8
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct EventDef
    {
        internal bool IsAdd; // AddとRemoveの2通り
        internal int X;
        internal int YMin;
        internal int YMax;
    }
    static List<EventDef> mEventList = new List<EventDef>();

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

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

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int X1 = wkArr[0];
            int Y1 = wkArr[1];
            int X2 = wkArr[2];
            int Y2 = wkArr[3];

            int XMin = Math.Min(X1, X2);
            int XMax = Math.Max(X1, X2);

            int YMin = Math.Min(Y1, Y2);
            int YMax = Math.Max(Y1, Y2);
            YMax--;

            EventDef WillAdd1;
            WillAdd1.IsAdd = true;
            WillAdd1.X = XMin;
            WillAdd1.YMin = YMin;
            WillAdd1.YMax = YMax;
            mEventList.Add(WillAdd1);

            EventDef WillAdd2;
            WillAdd2.IsAdd = false;
            WillAdd2.X = XMax;
            WillAdd2.YMin = YMin;
            WillAdd2.YMax = YMax;
            mEventList.Add(WillAdd2);
        }

        // X座標の昇順にソート
        mEventList = mEventList.OrderBy(pX => pX.X).ToList();

        var ImosDict = new Dictionary<long, long>();

        long Answer = 0;
        int UB = mEventList.Count - 1;
        for (int I = 0; I <= UB; I++) {
            Action<int, int> AddAct = (pKey, pVal) =>
            {
                if (ImosDict.ContainsKey(pKey) == false) {
                    ImosDict[pKey] = 0;
                }
                ImosDict[pKey] += pVal;
            };

            if (mEventList[I].IsAdd) {
                // いもす法での区間加算
                AddAct(mEventList[I].YMin, 1);
                AddAct(mEventList[I].YMax + 1, -1);
            }
            else {
                // いもす法での区間加算の打ち消し
                AddAct(mEventList[I].YMin, -1);
                AddAct(mEventList[I].YMax + 1, 1);
            }

            // 次でX座標がBreakするなら、面積を集計
            if (I == UB || mEventList[I].X < mEventList[I + 1].X) {
                long Area = DeriveArea(ImosDict);
                long RangeSta = mEventList[I].X;

                long RangeEnd = RangeSta;
                if (I < UB) {
                    RangeEnd = mEventList[I + 1].X - 1;
                }
                //Console.WriteLine("[{0},{1}]の面積は{2}", RangeSta, RangeEnd, Area);

                Answer += Area * (RangeEnd - RangeSta + 1);
            }
        }
        Console.WriteLine(Answer);
    }

    static long DeriveArea(Dictionary<long, long> pImosDict)
    {
        long[] KeysArr = pImosDict.Keys.ToArray();
        Array.Sort(KeysArr);

        long Answer = 0;
        long RunSum = 0;
        int UB = KeysArr.GetUpperBound(0);
        for (int I = 0; I <= UB; I++) {
            long CurrKey = KeysArr[I];

            RunSum += pImosDict[CurrKey];
            if (RunSum <= 0) continue;

            long NextKey = KeysArr[I + 1];

            Answer += NextKey - CurrKey;
        }
        return Answer;
    }
}

解説

X座標の昇順でイベントソートを行いつつ、
Y座標は、いもす法を使用してます。