문제

아이디어

CCW 알고리즘의 설명과도 같은 문제. 그렇다면 CCW 알고리즘이란 무엇일까?

CCW(Counter-ClockWise) 알고리즘

세 점이 주어졌을 때, 이 세 점이 반시계 방향으로 배열되어 있는지, 시계 방향으로 배열되어 있는지, 아니면 일직선에 있는지 판단하는 알고리즘.

세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 때, 벡터 P1-P2와 벡터 P2-P3를 외적했을 때의 결과가 음수라면 반시계 방향, 양수라면 시계방향, 0이라면 일직선을 의미한다.

신발끈 공식을 이용한다면 아래와 같이 표현할 수 있다.
CCW(P1, P2, P3) = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)

소스코드

import java.io.*;
import java.util.*;

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

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

    static int ccw(Point p1, Point p2, Point p3) {
        int ccw = (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
        return Integer.compare(ccw, 0);
    }

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

        st = new StringTokenizer(br.readLine());
        Point p1 = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        st = new StringTokenizer(br.readLine());
        Point p2 = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        st = new StringTokenizer(br.readLine());
        Point p3 = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));

        System.out.println(ccw(p1, p2, p3));
    }
}

채점결과