선분 교차 2(백준_17387)

https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

 

문제 설명

선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 구하는 문제이다. 이 때, 두 선분이 겹쳐도 교차하는 것이라고 생각한다.

 

문제에 대한 아이디어

이 문제를 풀기위해서는 CCW라는 알고리즘을 알고 있어야 한다. CCW는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘이다. 3개의 점을 A(X1, Y1) B(X2, Y2) C(X3, Y3) 라고 하자.

CCW = (X1Y2 + X2Y3 + X3Y1) - (X2Y1 + X3Y2 + X1Y3) 이다. 이 결과의 절댓값은 세 점의 백터의 외적값을 나타낸다,

• CCW < 0 : 시계 방향으로 이동
• CCW = 0 : 일직선
• CCW > 0 : 반시계 방향으로 이동

참고로 CCW 절댓값의 절반은 삼각형의 넓이이다.

 

CCW를 이용하여 문제풀기

선분이 교차 할 경우 3개의 점에서 CCW를 구하면 부호가 반대일 것이다.

그러므로 각각 CCW의 곱이 음수일 것이다.

반대로 교차를 안하게 되면 CCW의 값은 양수라는 것을 알 수 있다.

만약 일직선일 경우는 CCW의 값은 0일 것이다.

이때, 두 직선이 겹치는 지를 확인해야 한다.

이렇게 겹치게 되면 알 수 있는 것은 한점의 선분 AB의 x Max 값이 선분 CD의 x Min 값보다 크다는 것이다. 그러므로 모든 점을 각각 조사해 겹치는지 확인해보면 된다.

 

구현

• CCW

static int CCW(long x1, long y1, long x2, long y2, long x3, long y3){
    long temp = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
    if(temp > 0) return 1;
    else if(temp < 0) return -1;
    return 0;
}

• isOverlab(겹치는지 검사)

private static boolean isOverlab(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4){
    if(Math.min(x1, x2) <= Math.max(x3, x4) && Math.min(x3, x4) <= Math.max(x1, x2) && Math.min(y1, y2) <= Math.max(y3, y4) && Math.min(y3, y4) <= Math.max(y1,y2)) return true;
    return false;
}

• isCross

private static boolean isCross(long x1, long y1, long x2, long y2, long x3, long y3, long x4, long y4){
    int abc = CCW(x1,y1,x2,y2,x3,y3);
    int abd = CCW(x1,y1,x2,y2,x4,y4);
    int cda = CCW(x3,y3,x4,y4,x1,y1);
    int cdb = CCW(x3,y3,x4,y4,x2,y2);
    //일직선일 경우 겹치는지 검사
    if(abc * abd == 0 && cda * cdb == 0){
        return isOverlab(x1,y1,x2,y2,x3,y3,x4,y4);
    }else if(abc*abd <= 0 && cda * cdb <= 0) {return true;}
    return false;
}

• Main

public static void main(String []args) throws IOException {
    BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;
    st = new StringTokenizer(buf.readLine());
    long x1 = Integer.parseInt(st.nextToken());
    long y1 = Integer.parseInt(st.nextToken());
    long x2 = Integer.parseInt(st.nextToken());
    long y2 = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(buf.readLine());
    long x3 = Integer.parseInt(st.nextToken());
    long y3 = Integer.parseInt(st.nextToken());
    long x4 = Integer.parseInt(st.nextToken());
    long y4 = Integer.parseInt(st.nextToken());
    boolean cross = isCross(x1,y1,x2,y2,x3,y3,x4,y4);
    if (cross) System.out.println(1);
    else System.out.println(0);

}

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_17387.java

GitHub - Heron-Woong/CodingTest_Practice