ABC481-E Most Brilliant Starry Sky

問題へのリンク

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("3");
            WillReturn.Add("4");
            WillReturn.Add("2 1");
            WillReturn.Add("2 -1");
            WillReturn.Add("-1 2");
            WillReturn.Add("-2 -3");
            WillReturn.Add("3");
            WillReturn.Add("1 0");
            WillReturn.Add("2 1");
            WillReturn.Add("3 -2");
            WillReturn.Add("20");
            WillReturn.Add("351656128 486890400");
            WillReturn.Add("43833334 189818465");
            WillReturn.Add("244758369 410609525");
            WillReturn.Add("82390518 959687989");
            WillReturn.Add("37964139 450230904");
            WillReturn.Add("-27725133 788196612");
            WillReturn.Add("392638907 -544184247");
            WillReturn.Add("-305242056 -60014958");
            WillReturn.Add("-928747557 460755669");
            WillReturn.Add("-415081310 638281062");
            WillReturn.Add("307908966 -865172261");
            WillReturn.Add("580339611 459847409");
            WillReturn.Add("42654321 -744472144");
            WillReturn.Add("-286500328 34461456");
            WillReturn.Add("-874976232 -245368444");
            WillReturn.Add("462187336 508372206");
            WillReturn.Add("-229275227 74979882");
            WillReturn.Add("-180126519 740406850");
            WillReturn.Add("877877433 -211582842");
            WillReturn.Add("256315745 -928285605");
            //3
            //3
            //15
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct XYInfoDef
    {
        internal long X;
        internal long Y;
    }
    static List<XYInfoDef> mXYInfoList = new List<XYInfoDef>();

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        int CurrInd = 1;
        while (true) {
            if (CurrInd > InputList.Count - 1) break;
            mXYInfoList.Clear();
            mMonsterList.Clear();

            int N = int.Parse(InputList[CurrInd]);

            for (int I = CurrInd + 1; I <= CurrInd + 1 + N - 1; I++) {
                SplitAct(InputList[I]);
                XYInfoDef WillAdd;
                WillAdd.X = wkArr[0];
                WillAdd.Y = wkArr[1];
                mXYInfoList.Add(WillAdd);
            }
            Solve();
            CurrInd += N + 1;
        }
    }

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

    class MonsterDef : IComparable<MonsterDef>
    {
        internal long ID;
        internal long X;
        internal long Y;
        internal long Syougen;
        internal long DenseRank;
        internal bool IsDummy;

        public int CompareTo(MonsterDef pOtherIns)
        {
            // 第1ソートキーは象限
            if (Syougen != pOtherIns.Syougen) {
                return Syougen.CompareTo(pOtherIns.Syougen);
            }

            // 第2ソートキーはTangent
            if (Syougen % 2 == 1) {
                PointDef pA;
                PointDef pB;
                pA.X = X;
                pA.Y = Y;
                pB.X = pOtherIns.X;
                pB.Y = pOtherIns.Y;

                // Tangentでの降順なのでマイナスをかける
                return CompareTangent(pA, pB) * (-1);
            }
            return 0;
        }

        // --------------------------------------------------------
        // (静的メソッド)ソート済のListを引数として、dense_rankを設定
        // --------------------------------------------------------
        static internal void SetDenseRank(List<MonsterDef> pMonsterList)
        {
            long CurrDenseRank = 1;
            for (int I = 0; I <= pMonsterList.Count - 1; I++) {
                // 前と違ったらインクリメント
                if (I > 0) {
                    int Result = pMonsterList[I].CompareTo(pMonsterList[I - 1]);
                    if (Result != 0) {
                        CurrDenseRank++;
                    }
                }
                pMonsterList[I].DenseRank = CurrDenseRank;
            }
        }
    }
    static List<MonsterDef> mMonsterList = new List<MonsterDef>();

    // Tangentの大小関係での比較結果を返す
    static int CompareTangent(PointDef pA, PointDef pB)
    {
        if (pA.X == 0 && pB.X == 0) return 0;
        if (pA.X == 0 && pB.X != 0) return 1;
        if (pA.X != 0 && pB.X == 0) return -1;

        return (pA.Y * pB.X).CompareTo(pB.Y * pA.X);
    }

    static void Solve()
    {
        long N = mXYInfoList.Count;

        long CurrID = 0;
        foreach (XYInfoDef EachXYInfo in mXYInfoList) {
            var WillAdd1 = new MonsterDef();
            WillAdd1.ID = ++CurrID;
            long X = EachXYInfo.X;
            long Y = EachXYInfo.Y;
            WillAdd1.X = X;
            WillAdd1.Y = Y;
            WillAdd1.IsDummy = false;

            // 時計の0時から時計周りでの採番
            long Syougen = 0;
            if (X == 0 && Y > 0) Syougen = 0;
            if (X > 0 && Y > 0) Syougen = 1;
            if (X > 0 && Y == 0) Syougen = 2;
            if (X > 0 && Y < 0) Syougen = 3;

            if (X == 0 && Y < 0) Syougen = 4;
            if (X < 0 && Y < 0) Syougen = 5;
            if (X < 0 && Y == 0) Syougen = 6;
            if (X < 0 && Y > 0) Syougen = 7;

            WillAdd1.Syougen = Syougen;
            mMonsterList.Add(WillAdd1);

            var WillAdd2 = new MonsterDef();
            X *= -1;
            Y *= -1;
            WillAdd2.X = X;
            WillAdd2.Y = Y;
            WillAdd2.IsDummy = true;

            // 時計の0時から時計周りでの採番
            if (X == 0 && Y > 0) Syougen = 0;
            if (X > 0 && Y > 0) Syougen = 1;
            if (X > 0 && Y == 0) Syougen = 2;
            if (X > 0 && Y < 0) Syougen = 3;

            if (X == 0 && Y < 0) Syougen = 4;
            if (X < 0 && Y < 0) Syougen = 5;
            if (X < 0 && Y == 0) Syougen = 6;
            if (X < 0 && Y > 0) Syougen = 7;
            WillAdd2.Syougen = Syougen;
            mMonsterList.Add(WillAdd2);
        }
        mMonsterList.Sort();
        MonsterDef.SetDenseRank(mMonsterList);

        // DenseRankの最大値を求める
        long MaxDenseRank = mMonsterList.Max(pX => pX.DenseRank);

        // 個数[DenseRank]なフェニック木
        var Ins_Fenwick_Tree = new Fenwick_Tree(MaxDenseRank);
        foreach (MonsterDef EachMonster in mMonsterList) {
            if (EachMonster.IsDummy == false) {
                Ins_Fenwick_Tree[EachMonster.DenseRank]++;
            }
        }

        var DenseRankDict = new Dictionary<string, long>();
        foreach (MonsterDef EachMonster in mMonsterList) {
            string Hash = GetHash(EachMonster.X, EachMonster.Y);
            DenseRankDict[Hash] = EachMonster.DenseRank;
        }

        var Answerist = new List<long>();
        foreach (MonsterDef EachMonster in mMonsterList) {
            long RangeSta = EachMonster.DenseRank;
            long PairX = EachMonster.X * (-1);
            long PairY = EachMonster.Y * (-1);

            long RangeEnd = DenseRankDict[GetHash(PairX, PairY)];
            if (RangeSta < RangeEnd) {
                long RangeCnt = Ins_Fenwick_Tree.GetSum(RangeSta, RangeEnd);
                long Answer1 = RangeCnt;
                long Answer2 = RangeCnt - 1;
                Answerist.Add(Answer1);
                Answerist.Add(N - Answer1);
                Answerist.Add(Answer2);
                Answerist.Add(N - Answer2);
            }
        }
        Console.WriteLine(Answerist.Max());
    }

    static string GetHash(long pX, long pY)
    {
        return string.Format("{0},{1}", pX, pY);
    }
}

// フェニック木
#region Fenwick_Tree
internal class Fenwick_Tree
{
    private long[] mBitArr;
    private long mExternalArrUB;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ(外部配列のUBのみ指定)
    internal Fenwick_Tree(long pExternalArrUB)
    {
        mExternalArrUB = pExternalArrUB;

        // フェニック木の外部配列は0オリジンで、
        // フェニック木の内部配列は1オリジンなため、2を足す
        mBitArr = new long[pExternalArrUB + 2];
    }

    // コンストラクタ(初期化用の配列指定)
    internal Fenwick_Tree(long[] pArr)
        : this(pArr.GetUpperBound(0))
    {
        for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
            this.Add(I, pArr[I]);
        }
    }

    // コンストラクタ(初期化用のList指定)
    internal Fenwick_Tree(List<long> pList)
        : this(pList.Count - 1)
    {
        for (int I = 0; I <= pList.Count - 1; I++) {
            this.Add(I, pList[I]);
        }
    }

    // インデクサ
    internal long this[long pInd]
    {
        get { return GetSum(pInd, pInd); }
        set { Add(pInd, value - GetSum(pInd, pInd)); }
    }

    // [pSta,pEnd] のSumを返す
    internal long GetSum(long pSta, long pEnd)
    {
        return GetSum(pEnd) - GetSum(pSta - 1);
    }

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd)
    {
        pEnd++; // 1オリジンに変更

        long Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            pEnd -= pEnd & -pEnd;
        }
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(long pI, long pX)
    {
        pI++; // 1オリジンに変更

        while (pI <= mBitArr.GetUpperBound(0)) {
            mBitArr[pI] += pX;
            pI += pI & -pI;
        }
    }
}
#endregion

解説

ABC442-E Laser Takahashiをふまえ、
まずモンスターごとに180度先にダミーモンスターを用意します。

偏角ソートの並び順でのdense_rankを振り、
dense_rankをIndとして、フェニック木を作成し、
モンスターなら1を加算、ダミーモンスターなら加算なし
を行います。

また、解の半円は、なるべく多くの点をカバーするので、
任意の点からの180度を全て試せば良いと分かります。

なので、モンスターごとに、
180度先までのモンスター数を、フェニック木を使って求め
解候補を全て求めれば解けます。
解候補は、半円の上と下の2通りあるので、
●モンスター数
●モンスター数 - 1
●全体 - モンスター数
●全体 - (モンスター数 - 1)
の4つが解候補になります。

積分の考え方で、180度からデルタだけ増減すれば、
上記の4通りの解候補が実現可能だと分かります。