[Java][BOJ 17386] 선분 교차1

문제 링크

문제 파악

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

• 세 점이 일직선 위에 있는 경우는 없다.

접근 방법

L1의 두 점을 기준으로, L2의 CCW의 부호가 반대로 나오면 교차, 아니면 0 출력

+ L2와 L1의 두 점의 관계도 봐야 선분 교차 판정이 가능하다. CD가 AB를 가로질러도 AB가 CD를 가로지르지 않는 특수 케이스를 배제할 수 없기 때문이다. 

코드 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int x1 = input.nextInt();
        int y1 = input.nextInt();
        int x2 = input.nextInt();
        int y2 = input.nextInt();
        int x3 = input.nextInt();
        int y3 = input.nextInt();
        int x4 = input.nextInt();
        int y4 = input.nextInt();
        
        if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) < 0
                && ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) < 0){
            System.out.println(1);
        }
        else System.out.println(0);
    }

    public static int ccw(long x1, long y1, long x2, long y2, long x3, long y3) {
        return (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3) > 0 ? 1 : -1;
    }
}

배우게 된 점

long type으로 변환해서 계산해야 오버플로우를 막을 수 있다. 

질문