CCW(Counter Clock-Wise)

CCW 알고리즘은 한 선과 한 점의 위치 관계를 구할 때 사용하는 알고리즘입니다. 한 선분 AB와 점 C가 일직선 상에 있는지, 반시계 방향에 있는지, 시계방향에 있는지를 알려줍니다. 이 알고리즘은 기하 문제를 푸는데 사용이 되며 이 알고리즘을 이용하는 알고리즘에는 대표적으로 Convex Hull이라는 알고리즘이 있습니다.

반시계방향 일직선 시계방향

이 알고리즘의 구현 방법은 점 A, B, C에서 AB와 BC 벡터의 외적을 통해 음수 값이 나오면 시계 방향, 0값이 나오면 일직선, 양수 값이 나오면 반시계 방향으로 판단하는 것입니다. 두 벡터의 외적은 두 벡터 Vx={Xx,Xy}, Vy={Yx,Yy}라고 했을 때 Xx*Yy-Xy*Yx입니다. 따라서 점 A, B, C가 A(x1,y1), B(x2,y2), C(x3,y3)라면 CCW값은 선분 AB의 벡터를 Vab라 하면, Vab(x2-x1,y2-y1), 선분 BC의 벡터를 Vbc라 하면, Vbc=(x3-x2,y3-y2)이고, 이 두 벡터를 외적하면 (x2-x1)*(y3-y2)-(y2-y1)*(x3-x2)이다.

입력	출력
첫 줄에 테스트케이스의 수 T가 주어집니다. 각 테스트케이스 첫 줄에 점 A,B,C의 x,y값이 주어집니다. {Ax Ay Bx By Cx Cy}	각 테스트케이스마다 세 점의 관계를 출력합니다. 반시계방향이면 1 일직선상이면 0 시계방향이면 -1
Sample Input	Sample Output
3 0 0 1 1 2 2 0 0 0 1 1 0 0 0 1 0 0 1	0 -1 1

import java.util.*;

public class Main {
    public static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    };

    public static int ccw(Point a, Point b, Point c) {
        Point ab = new Point(b.x - a.x, b.y - a.y);
        Point bc = new Point(c.x - b.x, c.y - b.y);
        int ret = ab.x * bc.y - ab.y * bc.x;
        if (ret > 0) return 1;
        else if (ret == 0) return 0;
        else return -1;
    }

    static int T;

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        Point P[] = new Point[3];
        T = scanner.nextInt();
        for (int i = 0; i < T; i++) {

            for (int j = 0; j < 3; j++) {
                int x = scanner.nextInt();
                int y = scanner.nextInt();
                P[j] = new Point(x, y);
            }
            int result = ccw(P[0], P[1], P[2]);
            System.out.println(String.valueOf(result));
        }
    }

}