[백준 11758번] CCW (C++, Python)

이번 포스트에서는 백준 알고리즘 문제인 CCW 를 포스트하겠습니다.

 

해당 문제는 solved.ac 기준으로 골드 5 에 위치한 문제입니다.

 

먼저 문제입니다.

입력으로 2차원 좌표 평면 위의 점 3개의 x, y값이 주어집니다. 이때, 점 3개를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하여 출력하는 문제입니다.

 

해당 문제는 점A, 점B, 점C 가 있을 때, C에서 B로가는 벡터, B에서 A로 가는 벡터의 외적곱을 통해 CCW값을 구할 수 있습니다.

 

벡터 CB는 (bx - cx, by - cy), 벡터 BA는 (ax - bx, ay - by) 로 정의되고, 이 두 벡터를 외적곱하면 

CCW = (bx - cx)*(ay - by) - (by - cy)*(ax - bx) 가 됩니다.

 

이때, CCW 값이 양수라면, 반시계 방향을 이루고, 음수라면 시계 방향, 0이라면 일직선을 이루고 있습니다.

 

그러므로 CCW 값을 통해 문제에서 요구한대로 1, -1, 0을 출력해줍니다.

 

아래는 C++ 코드입니다.

 

#include <iostream>
 
using namespace std;
 
int main() {
    int x1, x2, x3, y1, y2, y3;
    int ccw;
 
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
 
    ccw = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
 
    if(ccw == 0)
        cout << ccw;
    else
        cout << (ccw > 0) ? 1 : -1;
 
    return 0;

다음으로 Python 코드입니다.

 

x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
x3, y3 = map(int, input().split())
 
ccw = (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1)
 
if ccw == 0 :
    print("0")
elif ccw > 0 :
    print("1")
elif ccw < 0 :
    print("-1")

해당 문제는 벡터의 외적곱을 잘 이해하고 있으면 수식을 그대로 적용하면 되는 문제이지만, 저는 수학이 많이 부족해서 이해하는데 어려움을 겪었던 문제였습니다.

 

다음 포스트에서 또 다른 백준 알고리즘 문제로 포스팅하겠습니다. 감사합니다.