CGL_2_B: Intersection

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

// Q063 交差判定 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("0 0 3 0 1 1 2 -1");
            WillReturn.Add("0 0 3 0 3 1 3 -1");
            WillReturn.Add("0 0 3 0 3 -2 5 0");
            //1
            //1
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

    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);
            PointDef P1; P1.X = wkArr[0]; P1.Y = wkArr[1];
            PointDef P2; P2.X = wkArr[2]; P2.Y = wkArr[3];
            PointDef P3; P3.X = wkArr[4]; P3.Y = wkArr[5];
            PointDef P4; P4.X = wkArr[6]; P4.Y = wkArr[7];

            if (CCW(P1, P2, P3) * CCW(P1, P2, P4) <= 0 &&
                CCW(P3, P4, P1) * CCW(P3, P4, P2) <= 0) {
                Console.WriteLine(1);
            }
            else {
                Console.WriteLine(0);
            }
        }
    }

    static int CCW(PointDef pPointA, PointDef pPointB, PointDef pPointC)
    {
        const int COUNTER_CLOCKWISE = 1;
        const int CLOCKWISE = -1;
        const int ONLINE_BACK = 2;
        const int ONLINE_FRONT = -2;
        const int ON_SEGMENT = 0;

        PointDef VectorA;
        VectorA.X = pPointB.X - pPointA.X;
        VectorA.Y = pPointB.Y - pPointA.Y;

        PointDef VectorB;
        VectorB.X = pPointC.X - pPointA.X;
        VectorB.Y = pPointC.Y - pPointA.Y;

        // 外積 A*Bを求める
        int Cross = VectorA.X * VectorB.Y - VectorA.Y * VectorB.X;

        // Aの半時計回りの方向にBが存在する
        if (Cross > 0) {
            return COUNTER_CLOCKWISE;
        }

        // Aの時計回りの方向にBが存在する
        if (Cross < 0) {
            return CLOCKWISE;
        }

        // 3点が1直線にある場合

        // 内積がマイナスなら、ベクトルの向きは反対
        int Dot = VectorA.X * VectorB.X + VectorA.Y * VectorB.Y;
        if (Dot < 0) {
            return ONLINE_BACK;
        }

        long NormA = (long)VectorA.X * VectorA.X + (long)VectorA.Y * VectorA.Y;
        long NormB = (long)VectorB.X * VectorB.X + (long)VectorB.Y * VectorB.Y;
        if (NormA < NormB) {
            return ONLINE_FRONT;
        }
        return ON_SEGMENT;
    }
}

解説

外積と内積を使って、判定してます。