[Algorithm] CCW

Counter Clock Wise

점 A, B, C가 있을 때 3개의 점 A, B, C를 차례로 이은 직선의 모양을 알고자 할 때 유용한 기하 알고리즘이다.

세 점에 대해 다음의 3 가지 모양이 존재할 수 있다.

CCW의 3 가지 경우

 

귀찮으니까 코드로 보자.

AB와 BC 벡터를 구하고, 벡터를 Cross (외적) 연산하면 세 점 A, B, C의 관계를 알 수 있다.

 

반시계 방향 : 음수

시계 방향 : 양수

직선 : 0

#include <iostream>
using namespace std;
struct xy {
    int y, x;
};
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    xy A, B, C;
    cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y;
    xy AB = { B.y - A.y, B.x - A.x };
    //cout << AB.y << AB.x <<"\n";
    xy BC = { C.y - B.y, C.x - B.x };
    //cout << BC.y << BC.x <<"\n";
    int r = AB.x* BC.y - AB.y * BC.x;
    //cout << r;
    if (r > 0)cout << 1;
    else if (r < 0) cout << -1;
    else cout << 0;
        
    return 0;
}

 

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

11758번: CCW