ABC225-E フ

問題へのリンク

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("1 1");
            WillReturn.Add("2 1");
            WillReturn.Add("1 2");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10");
            WillReturn.Add("414598724 87552841");
            WillReturn.Add("252911401 309688555");
            WillReturn.Add("623249116 421714323");
            WillReturn.Add("605059493 227199170");
            WillReturn.Add("410455266 373748111");
            WillReturn.Add("861647548 916369023");
            WillReturn.Add("527772558 682124751");
            WillReturn.Add("356101507 249887028");
            WillReturn.Add("292258775 110762985");
            WillReturn.Add("850583108 796044319");
            //10
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct HuDef
    {
        internal long X1;
        internal long Y1;
        internal long X2;
        internal long Y2;
    }

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

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

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

        var HuList = new List<HuDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            HuDef WillAdd;
            WillAdd.X1 = wkArr[0];
            WillAdd.Y1 = wkArr[1] - 1;
            WillAdd.X2 = wkArr[0] - 1;
            WillAdd.Y2 = wkArr[1];
            HuList.Add(WillAdd);
        }
        HuList.Sort((A, B) =>
        {
            PointDef pA;
            PointDef pB;
            pA.X = A.X2;
            pA.Y = A.Y2;
            pB.X = B.X2;
            pB.Y = B.Y2;
            return Compare(pA, pB);
        });

        // 区間スケジューリング問題に帰着させる
        bool FirstFlag = true;
        long CurrX = -1;
        long CurrY = -1;
        long Answer = 0;
        foreach (HuDef EachHu in HuList) {
            if (FirstFlag) {
                CurrX = EachHu.X2;
                CurrY = EachHu.Y2;
                FirstFlag = false;
                Answer++;
            }
            else {
                PointDef pA;
                pA.X = CurrX;
                pA.Y = CurrY;
                PointDef pB;
                pB.X = EachHu.X1;
                pB.Y = EachHu.Y1;
                if (Compare(pA, pB) <= 0) {
                    CurrX = EachHu.X2;
                    CurrY = EachHu.Y2;
                    Answer++;
                }
            }
        }
        Console.WriteLine(Answer);
    }

    // Tanシータの大小関係での比較結果を返す
    static int Compare(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);
    }
}

解説

Tanシータの上限と下限が制限されると考えれば、
区間スケジュール問題に帰着させることができます。