방과후
ALGORITHM NOTE약 1분

BOJ 17387 - 선분 교차 2

벡터 외적 돌려 돌려

#algorithm#boj#gold#geometry#case-analysis#line-segment-intersection
아카이브로 돌아가기

문제 링크

문제

2차원 좌표 평면 위의 두 선분 L1L_1, L2L_2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1L_1의 양 끝 점은 (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2), L2L_2의 양 끝 점은 (x3,y3)(x_3, y_3), (x4,y4)(x_4, y_4)이다.

입력

첫째 줄에 L1L_1의 양 끝 점 x1x_1, y1y_1, x2x_2, y2y_2가, 둘째 줄에 L2L_2의 양 끝 점 x3x_3, y3y_3, x4x_4, y4y_4가 주어진다.

출력

L1L_1과 L2L_2가 교차하면 1, 아니면 0을 출력한다.

풀이

두 선분이 교차하는지는 CCW 판정을 이용해 계산할 수 있다. 각 선분의 양 끝점이 다른 선분을 기준으로 서로 다른 방향에 있는지, 그리고 일직선인 경우 구간이 겹치는지를 보면 된다.

코드에서는 네 점에 대한 CCW 값을 계산해 일반 교차와 일직선 겹침을 나눠 처리한다. 일직선인 경우는 좌표 범위 비교까지 해야 실제로 겹치는지 판단할 수 있다.

기하 공식 하나보다 예외 처리가 더 중요하다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static class Point implements Comparable<Point> {
        int x, y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        @Override
        public int compareTo(Point o) {
            if (this.x == o.x) return this.y - o.y;
            return this.x - o.x;
        }
    }
 
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        Point[][] points = new Point[2][2];
        for (int i = 0; i < 2; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++)
                points[i][j] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        Arrays.sort(points[0]);
        Arrays.sort(points[1]);
 
        System.out.println(solve(points));
    }
 
    static int solve(Point[][] points) {
        int ccw1 = ccw(points[0][0], points[0][1], points[1][0]);
        int ccw2 = ccw(points[0][0], points[0][1], points[1][1]);
        int ccw3 = ccw(points[1][0], points[1][1], points[0][0]);
        int ccw4 = ccw(points[1][0], points[1][1], points[0][1]);
 
        if (ccw1 != ccw2 && ccw3 != ccw4)   return 1;
        if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0)
            if (points[1][0].compareTo(points[0][1]) <= 0 && points[0][0].compareTo(points[1][1]) <= 0 )
                return 1;
        return 0;
    }
 
    static int ccw(Point a, Point b, Point c) {
        long cross = (long) (b.x - a.x) * (c.y - a.y) - (long) (c.x - a.x) * (b.y - a.y);
        if (cross > 0) return 1;
        else if (cross == 0) return 0;
        else return -1;
    }
}

복잡도

  • 시간 복잡도: O(1)O(1)
  • 공간 복잡도: O(1)O(1)

마무리

선분 교차 판정은 CCW가 핵심이지만, 진짜 중요한 건 일직선 예외 처리다. 일반 경우와 경계 경우를 나눠 보면 깔끔하게 해결된다.