第13回PAST J 横断

問題へのリンク

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("4 3");
            WillReturn.Add("-2 0 2 0");
            WillReturn.Add("2 1 2 7");
            WillReturn.Add("0 1 10 10");
            WillReturn.Add("1 0 -1 3");
            WillReturn.Add("-1 1 0 5");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2");
            WillReturn.Add("0 0 0 0");
            WillReturn.Add("1 2 3 4");
            WillReturn.Add("2 4 6 8");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("20 17");
            WillReturn.Add("-6 -77 40 99");
            WillReturn.Add("-14 74 -48 27");
            WillReturn.Add("-51 43 5 89");
            WillReturn.Add("-39 -29 80 75");
            WillReturn.Add("-55 59 17 39");
            WillReturn.Add("-37 -68 38 62");
            WillReturn.Add("14 31 43 49");
            WillReturn.Add("49 -7 -65 13");
            WillReturn.Add("-40 -45 36 32");
            WillReturn.Add("-54 -43 99 77");
            WillReturn.Add("-94 57 -22 12");
            WillReturn.Add("-85 67 -46 72");
            WillReturn.Add("95 68 55 67");
            WillReturn.Add("-56 51 -38 22");
            WillReturn.Add("32 -19 65 46");
            WillReturn.Add("76 66 -53 8");
            WillReturn.Add("35 -78 -41 30");
            WillReturn.Add("-51 -85 24 64");
            WillReturn.Add("45 -53 82 12");
            WillReturn.Add("39 19 -52 86");
            WillReturn.Add("-11 -67 -33 100");
            //694
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;
    static long mSX;
    static long mSY;
    static long mTX;
    static long mTY;

    class LineDef
    {
        internal long P;
        internal long Q;
        internal long R;
        internal long W;
        internal bool IsDivision; // 始点と終点を分断するか？
    }
    static List<LineDef> mLineList = new List<LineDef>();

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

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

        SplitAct(InputList[0]);
        long K = wkArr[1];

        SplitAct(InputList[1]);
        mSX = wkArr[0];
        mSY = wkArr[1];
        mTX = wkArr[2];
        mTY = wkArr[3];

        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            var WillAdd = new LineDef();
            WillAdd.P = wkArr[0];
            WillAdd.Q = wkArr[1];
            WillAdd.R = wkArr[2];
            WillAdd.W = wkArr[3];
            WillAdd.IsDivision = false;
            mLineList.Add(WillAdd);
        }

        // 始点と終点を分断するかを設定
        SetIsDivision();

        long Answer = 0;
        long Rest = K;
        foreach (LineDef EachLine in mLineList.OrderBy(pX => pX.IsDivision).ThenBy(pX => pX.W)) {
            if (EachLine.IsDivision) {
                Answer += EachLine.W;
            }
            if (--Rest == 0) break;
        }
        Console.WriteLine(Answer);
    }

    // 始点と終点を分断するかを設定
    static void SetIsDivision()
    {
        for (int I = 0; I <= mLineList.Count - 1; I++) {
            long P = mLineList[I].P;
            long Q = mLineList[I].Q;
            long R = mLineList[I].R;

            // 場合1 Y=定数 な直線
            if (P == 0) {
                // SYもTYも、直線の上側にある場合
                if (R < Q * mSY && R < Q * mTY) {
                    continue;
                }

                // SYもTYも、直線の下側にある場合
                if (R > Q * mSY && R > Q * mTY) {
                    continue;
                }
            }

            // 場合2 X=定数 な直線
            if (Q == 0) {
                // SYもTYも、直線の右側にある場合
                if (R < P * mSX && R < P * mTX) {
                    continue;
                }

                // SYもTYも、直線の左側にある場合
                if (R > P * mSX && R > P * mTX) {
                    continue;
                }
            }

            // 場合3 Y=AX+B な直線
            if (P != 0 && Q != 0) {
                bool Result1 = (-P * mSX + R > Q * mSY);
                bool Result2 = (-P * mTX + R > Q * mTY);

                if (Result1 && Result2) {
                    continue;
                }

                if (Result1 == false && Result2 == false) {
                    continue;
                }
            }

            mLineList[I].IsDivision = true;
        }
    }
}

解説

以下の場合分けをし、
始点と終点が直線によって分断されてるかを判定してます。

場合1 Y=定数
場合2 X=定数
場合3 Y=AX+B