P.17387 선분 교차 2

코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;

public class Main {

    static public class Point implements Comparable{
        long x, y;

        public Point(long x, long y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Object o) {
            Point point = (Point) o;

            if (point.x == this.x) return (int) (this.y - point.y);
            else return (int) (this.x - point.x);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Point[] points = new Point[4];
        long[] line = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        points[0] = new Point(line[0], line[1]);
        points[1] = new Point(line[2], line[3]);
        line = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        points[2] = new Point(line[0], line[1]);
        points[3] = new Point(line[2], line[3]);

        bw.write(Integer.toString(checkIntersect(points)));
        bw.flush();
    }

    private static int checkIntersect(Point[] points) {
        int cp1 = crossProduct(points[0], points[1], points[2]), cp2 = crossProduct(points[0], points[1], points[3]);
        int cp3 = crossProduct(points[2], points[3], points[0]), cp4 = crossProduct(points[2], points[3], points[1]);

        if (cp1 * cp2 <= 0 && cp3 * cp4 <= 0) {
            if (cp1 * cp2 == 0 && cp3 * cp4 == 0) {
                Point temp;
                if (points[0].compareTo(points[1]) > 0) {
                    temp = points[0];
                    points[0] = points[1];
                    points[1] = temp;
                }
                if (points[2].compareTo(points[3]) > 0) {
                    temp = points[2];
                    points[2] = points[3];
                    points[3] = temp;
                }

                if (points[0].compareTo(points[3]) <= 0 && points[1].compareTo(points[2]) >= 0) return 1;
                else return 0;
            }
            return 1;
        }
        else return 0;
    }

    private static int crossProduct(Point p1, Point p2, Point p3) {
        long res = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

        if (res > 0) return 1;
        else if (res == 0) return 0;
        else return -1;
    }
}

코드 설명

초반엔 직선의 방정식으로 접근을 했지만 y축에 있는 직선일 경우 기울기가 Infinity가 나오면서 케이스가 너무 많아져 다른 방법을 생각해봤다.

 

새 아이디어는 선분이 교차할 때 한 점에서 다른 선분의 점들을 바라볼 때 그 방향이 서로 다르다는 것에서 시작했다.

외적으로 방향을 판별해낼 수 있다는 것까진 알게 되었는데 두 벡터를 외적할 때 각도를 구해서 계산하는 것은 너무 비효율적이었다.

그래서 시선을 점->점이 아닌 선분->점으로 바꿨다.

선분과 점으로 볼 때 교차 여부가 달라지지 않을 뿐더러 세 점이라면 신발끈으로 쉽게 외적을 구할 수 있기 때문이다.

 

초록색 선분과 파란색 각 점을 이용하여 두 개의 삼각형을 그려보았을 때 그림은 다음과 같은데 두 삼각형의 방향이 다른 것을 알 수 있다.

초록색 선분 기준

 

파란색 선분 기준

 

그럼 이제 선분이 위치할 수 있는 조건에 따라서 검증을 해보자.

 

일단 교차하지 않는 경우는 다음과 같다.

1. 평행한다
2. 평행을 제외하고 교차하지 않는 경우

1. 평행한다

평행할 경우, 위의 아이디어에 맞게 두 삼각형의 방향이 일치한다.

2번의 교차하지 않는 경우에서,

위쪽 그림은 빨간색과 주황색 삼각형의 방향이 같은 방향을 바라보고 있지만

아래쪽 그림은 빨간색과 주황색 삼각형의 방향이 다른 방향을 바라보고 있다.

 

따라서 벡터의 외적을 구할 때 두 선분을 기준으로 했을 때를 모두 확인해야 한다.

 

교차하는 선분들 중 하나 더 확인해야 할 것이 있다.

바로 겹칠 때이다.

빨간색 점 : 초록 선분의 양 끝 / 노란색 점 : 파란 선분의 양 끝

각 선분의 선들이 크기 순이라고 가정했을 때,

초록 선분의 오른쪽 점은 파란 선분의 왼쪽 점보다 크거나 같아야하며, 초록선분의 왼쪽 점은 파란 선분의 오른쪽 점보다 작거나 같아야 한다.

 

---

CCW라는 알고리즘이 위 아이디어의 내용인 듯하다.

내가 봐도 내가 그린 그림이 너무 헷갈려서 이것만 읽어봐도 될 것 같다.

https://www.acmicpc.net/blog/view/27

점 3개의 방향성을 나타내는 CCW