[알고리즘] CCW(백준11758번)_골드5_기하학, 기하, 벡터, 외적, 신발끈

문제링크

📝 문제

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

 

예제 입력 1

1 1
5 5
7 3

예제 출력 1

-1

예제 입력 2

1 1
3 3
5 5

예제 출력 2

0

예제 입력 3

1 1
7 3
5 5

예제 출력 3

1

---

🔍 정답

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

public class Main {

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int x1 = Integer.parseInt(st.nextToken());
        int y1 = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int x2 = Integer.parseInt(st.nextToken());
        int y2 = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int x3 = Integer.parseInt(st.nextToken());
        int y3 = Integer.parseInt(st.nextToken());

        // 외적(cross product) 공식, 신발끈 공식이라고도 함!
        int cp = (x1*y2 + x2*y3 + x3*y1) - (x2*y1 + x3*y2 + x1*y3);

        // 외적이 양수이면 시계방향, 음수이면 반시계방향이며 0이라면 평행인 것!
        if (cp > 0)
            System.out.println(1);
        else if (cp < 0)
            System.out.println(-1);
        else
            System.out.println(0);
    }
}

• CCW는 기하 알고리즘의 입문으로 유명하다고 한다. 입문 문제답게 간단하지만 기하 문제답게 무슨 소린지 알아들을 수가 없었다. 벡터는 뭐고 외적은 무엇인지...
• 단순하게 신발끈 공식만 외워서 풀어도 되지만 그래도 조금이나마 개념을 정리하고 가는 것이 좋을 것 같아서 아주아주 간단하게 정리해보았다.

 

CCW(Counter-ClockWise)

• CCW는 평면에 놓여진 세 점의 방향관계를 구하는 알고리즘이다.
• 문제에서와 같이 세 점이 시계 방향인지, 반시계 방향인지 혹은 직선 방향인지를 구해서 시계 방향일 때는 양수, 반시계 방향일 때는 음수, 직선일 때는 0을 반환하게 된다.
• 기본적으로 세 점을 이용해 두 개의 벡터를 그리고 그 벡터의 외적의 부호를 통해 판별하게 된다.

 

벡터(Vector)

• 벡터 개념에 앞서 주의해야 할 점은, 수학이나 기하학에서의 벡터와 컴퓨터과학에서의 벡터는 개념이 다르다.
• 컴퓨터과학에서의 벡터는 순서가 있는 List를 의미한다고 한다.
• 하지만 이 문제는 기하 알고리즘이므로 기하학에서의 벡터의 개념인 크기와 방향을 갖는 물리량을 따라야 하고 단순화해서 화살표의 방향 을 벡터라고 생각하고자 한다.

• A에서 B로 가는 화살표에서 보았을 때, C는 직선이고 D는 반시계 방향이며 E는 시계 방향이 된다. 여기서 유추해볼 수 있는 것은 선이 그려지는 순서에 따라 답이 달라질 수 있다는 것!

 

외적(cross product)

• 외적은 두 벡터에 동시에 수직인 벡터를 구하는 연산이라고 한다.

• 위 그림에서 빨간선이 두 벡터에 동시에 수직인 벡터인 수직벡터이다.
• 모양이 같은데 왜 방향이 다른 것일까?
• 이는 두 벡터를 연산하는 순서에 따라 수직벡터가 달라진다는 것을 의미한다!

 

• 공대의 만능 법칙인 오른손 법칙을 설명하는 그림이라고 한다.
• A에서 B 방향으로 움직인다고 볼 때 손가락을 같은 방향으로 접었을 때 엄지 손가락이 향하는 위치가 수직벡터의 방향이 된다.
• 흔히 수직벡터의 좌표를 z 로 표현하는데, 만약 연산을 반대로 한다면 z좌표의 부호가 반대가 될 것이다!
• 외적의 부호로 세 점의 방향 관계(CCW)를 구할 수 있다는 것 정도로만 알고 넘어가보겠다!

 

신발끈 공식

 

• 두 직선에 대한 외적값을 구하는 신발끈 공식이다.
• X1과 Y1을 끝에 하나씩 더 써준 후 같은 검정색 선끼리의 곱은 더하고 빨간색 선의 곱은 빼주면 된다.

CCW = (X1*Y2 + X2*Y3 + X3*Y1) - (X2*Y1 + X3*Y2 + X1*Y3)

• 위에서 구한 값의 부호에 따라 방향 관계를 판별하면 된다!