[백준] 17387번 - 선분 교차 2 (Gold 2)

문제 링크

백준 17387번 - 선분 교차 2 (Gold 2)

문제 설명

2차원 평면 상의 선분 두 개가 주어져있을 때, 선분들이 교차하는지 여부를 출력한다.
두 선분이 일치하거나, 선분의 끝 점이 다른 선분 위에 있는 것도 교차하는 것으로 간주한다.

정답 코드 및 설명

$(x_1, y_1), (x_2, y_2)$를 지나는 직선의 방정식은 $f(x, y) = (y_2 - y_1)(x - x_1) + (x_2 - x_1)(y - y_1) = 0$이다.
$f(x, y)$가 0이라면 $(x, y)$가 직선 상의 점이며, 양수라면 직선보다 오른쪽에, 음수라면 직선보다 왼쪽에 있다.
두 선분의 교점이 있는 경우는 아래의 두 가지 경우로 나눌 수 있다.

1. 두 선분이 말 그대로 교차한다.
   • $(x_1, y_1), (x_2, y_2)$는 $(x_3, y_3), (x_4, y_4)$를 지나는 직선을 기준으로 서로 반대편에 위치한다.
   • $(x_3, y_3), (x_4, y_4)$는 $(x_1, y_1), (x_2, y_2)$를 지나는 직선을 기준으로 서로 반대편에 위치한다.
2. 한 선분의 끝 점이 다른 선분 위에 있다.
   • $(x_3, y_3)$이 선분 $(x_1, y_1), (x_2, y_2)$ 위에 있다.
   • $(x_4, y_4)$이 선분 $(x_1, y_1), (x_2, y_2)$ 위에 있다.
   • $(x_1, y_1)$이 선분 $(x_3, y_3), (x_4, y_4)$ 위에 있다.
   • $(x_2, y_2)$이 선분 $(x_3, y_3), (x_4, y_4)$ 위에 있다.

이를 코드로 표현하면 아래와 같다.

import java.io.*;
import java.util.StringTokenizer;

public class BOJ17387 {

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

        long[][] points = new long[4][2];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {
            points[i / 2][i % 2] = Integer.parseInt(st1.nextToken());
            points[i / 2 + 2][i % 2] = Integer.parseInt(st2.nextToken());
        }
        long[] calc = calc(points);
        int ans = 0;
        // 1의 경우
        // f(x, y)와 f(z, w)의 부호가 반대라는 것은 (x, y)와 (z, w)가 도형 f를 경계로 반대편에 있음을 뜻한다.
        if ((double) calc[0] * calc[1] < 0 && (double) calc[2] * calc[3] < 0)
            ans = 1;
        // 2-1의 경우
        if (calc[2] == 0 && (points[0][0] - points[2][0]) * (points[0][0] - points[3][0]) <= 0
                && (points[0][1] - points[2][1]) * (points[0][1] - points[3][1]) <= 0)
            ans = 1;
        // 2-2의 경우
        if (calc[3] == 0 && (points[1][0] - points[2][0]) * (points[1][0] - points[3][0]) <= 0
                && (points[1][1] - points[2][1]) * (points[1][1] - points[3][1]) <= 0)
            ans = 1;
        // 2-3의 경우
        if (calc[0] == 0 && (points[2][0] - points[0][0]) * (points[2][0] - points[1][0]) <= 0
                && (points[2][1] - points[0][1]) * (points[2][1] - points[1][1]) <= 0)
            ans = 1;
        // 2-4의 경우
        if (calc[1] == 0 && (points[3][0] - points[0][0]) * (points[3][0] - points[1][0]) <= 0
                && (points[3][1] - points[0][1]) * (points[3][1] - points[1][1]) <= 0)
            ans = 1;
        bw.write(ans + "");
        bw.close();
    }

    static long[] calc(long[][] points) {
        long[] calc = new long[4];
        // point2는 point0, 1 잇는 직선과 위치 비교
        calc[0] = (points[1][1] - points[0][1]) * (points[2][0] - points[0][0])
                + (points[0][0] - points[1][0]) * (points[2][1] - points[0][1]);
        // point3은 point0, 1 잇는 직선과 위치 비교
        calc[1] = (points[1][1] - points[0][1]) * (points[3][0] - points[0][0])
                + (points[0][0] - points[1][0]) * (points[3][1] - points[0][1]);
        // point0은 point1, 2 잇는 직선과 위치 비교
        calc[2] = (points[3][1] - points[2][1]) * (points[0][0] - points[2][0])
                + (points[2][0] - points[3][0]) * (points[0][1] - points[2][1]);
        // point1은 point1, 2 잇는 직선과 위치 비교
        calc[3] = (points[3][1] - points[2][1]) * (points[1][0] - points[2][0])
                + (points[2][0] - points[3][0]) * (points[1][1] - points[2][1]);
        return calc;
    }
}