[백준 17386] 선분 교차 1

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

17386번: 선분 교차 1

 

 

 

작년 알설 수업 때 배웠던 거다...

근데 문제 풀때 하나도 기억 안났음

당연히 그 때 관련 문제를 안풀었고 공식만 외웠으니까!!!!!!!

 

그래서 다시 구글링을 해서 공부를 해봤다.

 

CCW(CounterClockWise)

세 점에 대한 방향을 나타냄.

 

점 A, B, C가 있을 때, 세 가지 경우가 존재한다

 

 

 

1)

A->B 방향이 B->C 방향에 대해 반시계 방향인 경우

 

 

2)

A->B 방향이 B->C 방향에 대해 시계 방향인 경우

 

 

 

3)

세 점이 평행한 경우

 

 

 

 

 

위 선분들의 방향을 계산하는 CCW 값은 다음과 같다. (이 식은 외적에 의하여 계산됨.)

 

(Bx - Ax)(Cy - Ay) - (By - Ay)(Cx - Ax)

 

1)의 반시계 경우에는 0보다 큰 값이,

2)의 시계 경우에는 0보다 작은 값이,

3) 평행한 경우에는 0의 값으로 계산해 낼 수 있다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Main {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        double segment1[] = new double[4];
        double segment2[] = new double[4];
        String line = br.readLine();
        segment1 = Arrays.stream(line.split(" ")).mapToDouble(Double::parseDouble).toArray();
        line = br.readLine();
        segment2 = Arrays.stream(line.split(" ")).mapToDouble(Double::parseDouble).toArray();

        if(isCross(segment1,segment2) && isCross(segment2,segment1))
            System.out.println(1);
        else
            System.out.println(0);
    }

    private static boolean isCross(double arr1[], double arr2[]) {
        boolean flag1=(arr1[0]*arr1[3]+arr1[2]*arr2[1]+arr2[0]*arr1[1]
                        -arr1[2]*arr1[1]-arr2[0]*arr1[3]-arr1[0]*arr2[1])>0;
        boolean flag2=(arr1[0]*arr1[3]+arr1[2]*arr2[3]+arr2[2]*arr1[1]
                -arr1[2]*arr1[1]-arr2[2]*arr1[3]-arr1[0]*arr2[3])>0;

        return flag1 ^ flag2;
    }
}

 

 

 

---

https://jason9319.tistory.com/358

CCW와 CCW를 이용한 선분 교차 판별

 

CCW에 대한 정의

https://degurii.tistory.com/47

[알고리즘] CCW로 세 점의 방향성 판별하기