ABC266-C Convex Quadrilateral

問題へのリンク

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("0 0");
            WillReturn.Add("1 0");
            WillReturn.Add("1 1");
            WillReturn.Add("0 1");
            //Yes
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0 0");
            WillReturn.Add("1 1");
            WillReturn.Add("-1 0");
            WillReturn.Add("1 -1");
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    // 逆ベクトルを求める
    static PointDef DeriveInvVect(PointDef pVect)
    {
        PointDef InvVect;
        InvVect.X = -pVect.X;
        InvVect.Y = -pVect.Y;
        return InvVect;
    }

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

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

        var PointList = new List<PointDef>();
        foreach (string EachStr in InputList) {
            SplitAct(EachStr);
            PointDef WillAdd;
            WillAdd.X = wkArr[0];
            WillAdd.Y = wkArr[1];
            PointList.Add(WillAdd);
        }

        var ResultList = new List<bool>();
        PointDef Vect0 = SetVector(PointList[0], PointList[1]);
        PointDef Vect1 = SetVector(PointList[1], PointList[2]);
        PointDef Vect2 = SetVector(PointList[2], PointList[3]);
        PointDef Vect3 = SetVector(PointList[3], PointList[0]);

        ResultList.Add(IsMore180(DeriveInvVect(Vect1), Vect0));
        ResultList.Add(IsMore180(DeriveInvVect(Vect2), Vect1));
        ResultList.Add(IsMore180(DeriveInvVect(Vect3), Vect2));
        ResultList.Add(IsMore180(DeriveInvVect(Vect0), Vect3));

        if (ResultList.Exists(pX => pX)) {
            Console.WriteLine("No");
        }
        else {
            Console.WriteLine("Yes");
        }
    }

    static bool IsMore180(PointDef pVect1, PointDef pVect2)
    {
        long Cross = DeriveCross(pVect1, pVect2);
        return Cross < 0;
    }

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

    // 外積を求める
    static long DeriveCross(PointDef pVector1, PointDef pVector2)
    {
        return pVector1.X * pVector2.Y - pVector1.Y * pVector2.X;
    }
}

解説

ベクトルの外積を使ってます。

別解その1で
アンドリューのアルゴリズムで凸包の座標を求めて、
凸包が四角形かで判定することもできます。
CGL_4_A: Convex Hull

別解その2で
2本の対角線の線分が交点を持つかで、判定することもできます。