[백준] 11758번 CCW

Geometry 정복해보자!

문제

기초 지식

Geometry 즉 기하 알고리즘들의 기초가 되어지는 CCW알고리즘을 알아볼 수 있는 문제이다. CCW는 Counter clockwise의 약자로써, 평면 위에 놓여진 세점의 방향관계를 알아내는 알고리즘이다.

외적

ccw를 이해하기 위해서는 외적에 대한 기초 지식이 있어야 한다. Geometry 특성상 이해하여서 푸는 것이 중요하다고 생각한다.

외적의 정의

외적의 정의는 아래와 같다. \(\overrightarrow{a}\times \overrightarrow{b}=(\vert\overrightarrow{a}\vert\vert\overrightarrow{b}\vert sin\theta)\overrightarrow{n})\) 이때 \(\theta\)가 0혹은 \(\pi\)이면 외적값이 0이 되므로 3점이 일직선에 있는 경우라는 것을 알 수 있다.

이외의 경우에는 \(\overrightarrow{n}\) 에 의해 음수가 되거나 양수가 되어지는데 이는 오른손 법칙을 따른다. 이때 오른손 법칙은 아래와 같은 방식이 되어진다.

이때 우리는 보통 2차원에서의 외적을 통해 알 수 있다. \(\overrightarrow{n} - \hat{k}\) 이면 3점이 반시계, \(\overrightarrow{n} - \hat{k}\) 이면 3점이 시계이다. 이를 설명하는것이 아래와 같은 그림이다.

이는 사람이 알면 자명하지만, 이것을 알고리즘으로 적용하려면, 벡터의 외적값을 구하면 간단히 풀이 할 수 있다. 이는 3점의 방향성을 확인하면서 이해해보면된다.

####평면위에서 3점의 방향성 판별 \(\overrightarrow{a} = \overrightarrow{AB} = (x_2 - x_1, y_2 - y_1, 0), \overrightarrow{b} = \overrightarrow{AC} = (x_3 - x_1, y_3 - y_1, 0)\) 이므로 \(\overrightarrow{a}\times \overrightarrow{b} = (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1)\) 이다.

외적값이 0이면 3점이 한직선에 존재한다. 외적값이 양수이면 3점이 반시계로 존재한다. 외적값이 음수이면 3점이 시계로 존재한다.

문제 풀이

---

전체코드 자세히 보기

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int ccw(vector<pair<int, int>> p)
{
    return (p[1].first - p[0].first) * (p[2].second - p[0].second) - (p[1].second -p[0].second) * (p[2].first - p[0].first);
}
int main(void){
    vector<pair<int, int>> p(3, {0, 0});
    for(int i = 0; i < 3; i++)
        cin >> p[i].first >> p[i].second;
    if(ccw(p) >0)
        cout << "1\n";
    else if(ccw(p) == 0)
        cout << "0\n";
    else
        cout << "-1\n";
    return 0;
}

---

문제 결과

문제 출처 https://www.acmicpc.net/problem/11758

CCW 관련 출처 https://degurii.tistory.com/47