[백준 #11758 c++] CCW

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

11758번: CCW

 

겉보기에는 단순한 문제이다.

세 점이 이루는 두 선분의 방향이 시계인지 반시계인지를 알아내는 것은 딱 생각했을 때 다음과 같다.

 

점 A, B, C를

A(x1,  y1), B(x2, y2), C(x3, y3) 라고 정의할 때,

 

점AB가 이루는 직선상에 점C가 있는 경우 0을 출력하면 된다.

그리고 직선상에 있지 않은 경우에는 둘로 나눠지는데,

 

점A보다 점B가 오른쪽에 있는 경우 우상향 또는 우하향 직선이 되고 즉,

x1 < x2 인 경우,

점C가 직선AB보다 위에 있을 때에는 반시계 방향이 된다.

 

반면 점B가 점A의 왼쪽에 있는 경우 좌상향 또는 좌하향 직선이 되고 즉,

x1 > x2 인 경우,

점C가 직선AB보다 위에 있을 때에는 시계방향이 된다.

 

그냥 이렇게 푼 결과를 코드로 나타내면 다음과 같다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

struct Coordinate {
    int x;
    int y;
};

struct Linear {
    double gradient;
    double yIntercept;
};

int getPosY(Linear func, Coordinate coord) {
    double fy = coord.x * func.gradient + func.yIntercept;
    if (coord.y > fy) return 1;
    else if (coord.y == fy) return 0;
    else return -1;
}

Linear getLinear(Coordinate c1, Coordinate c2) {
    Linear lin;
    lin.gradient = (double)(c2.y - c1.y) / (c2.x - c1.x);
    lin.yIntercept = c1.y - lin.gradient * c1.x;
    return lin;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    vector<Coordinate> v;
    int n = 3;
    while (n--) {
        Coordinate coord;
        cin >> coord.x >> coord.y;
        v.push_back(coord);
    }

    Linear lin = getLinear(v[0], v[1]);
    int result = getPosY(lin, v[2]);
    if (!result) cout << 0;
    else {
        if (v[1].x - v[0].x > 0) {
            cout << result;
        }
        else {
            cout << result * -1;
        }
    }
    
    return 0;
}

 

하지만 이 코드는 컴퓨터가 실수를 저장하는 방법을 간과했다.

컴퓨터는 부동소수점으로 실수를 저장하기 때문에 0.1 같은 숫자를 완벽하게 표현하지 못한다.

즉, 점C가 직선상에 있어야 하지만 간발의 차이로 직선보다 위에 있다고 계산해버릴 수 있다.

 

그래서 이 문제는 직접 풀기보다는 CCW 알고리즘을 한 번 검색해서 풀어보는 것을 권하는 것이다.

---

CCW: Counter Clockwise

평면위에 찍힌 세 점이 이루는 선분의 방향을 찾는 알고리즘이다.

하지만 위의 방법과 달리 부동소수점이 아닌 정수형으로만 계산하기 때문에 오차가 발생하지 않는다.

 

그리고 이 알고리즘을 이해하기 위해서는 선형대수학, 그 중에서도 벡터의 외적의 개념을 알아야 한다.

 

다시 중고등학교 시절로 돌아가보자.

벡터의 외적의 정의는 3x3행렬의 곱이며 그 크기가 두 벡터가 이루는 평행사변형의 넓이와 같다고도 하지만,

더 쉽게 설명하면 3차원 공간상에서 두 벡터와 수직인 법선 벡터를 말한다.

 

이와 관련한 정보는 다른 곳에 찾으면 다 나오고 여기서는 문제와 관련한 외적 공식만 적용한다.

 

벡터의 외적은 기본적으로 3차원 공간상의 두 벡터를 다루기 때문에 이를 2차원 평면으로 변환해야 한다.

이 때 외적 공식을 보면,

 

두 벡터 A(a1, a2, a3), B(b1, b2, b3) 가 이루는 각을 θ, 법선 벡터를 N이라 할 때 외적 A X B(A cross B)는

A X B = (|A||B|sinθ)N = (a2b3 - a3b2, a3b1 - a1b3, a1b2 - a2b1)

으로 정의된다. (|A|는 벡터A의 크기를 나타낸다.)

 

여기서 우리는 2차원 평면상의 두 벡터를 다루기 때문에 a3 = 0, b3 = 0 이므로

A X B = (0, 0, a1b2 - a2b1)

로 x, y값을 모두 0으로 만들어 버릴 수 있다.

그리고 이 결과는 딱 봐도 평면과 수직인 법선 벡터임을 알 수 있다.

(여기서 a1b2 - a2b1은 2x2 행렬의 역행렬 공식에 있는 ad-bc 로 이해하면 외우기 쉽다.)

---

 

벡터A = 점A에서 점B로 가는 벡터 = 점B - 점A

벡터B = 점A에서 점C로 가는 벡터 = 점C - 점A

라고 해보자.

 

벡터A(a1, a2), 벡터B(b1, b2)에 대해

a1b2 - a2b1을 각 점의 좌표값의 식으로 전개하면

각 점의 좌표를 (x1, y1), (x2, y2), (x3, y3) 라고 할 때

a1 = x2 - x1, a2 = y2 - y1

b1 = x3 - x1, b2 = y3 - y1 이므로

a1b2 - a2b1 = (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) 이 된다.

 

우리는 a1b2 - a2b1의 값을 놓고

양수라면 (오른손 법칙에 의해) 반시계 방향이 되고

음수라면 시계 방향이 됨을 알 수 있다.

 

0이라면 직선상에 놓였다고 볼 수 있는데, 그 이유는

위의 벡터의 정의에서 직선상에 놓인 경우는 두 벡터가 이루는 각이 0 또는 180도가 된다는 의미이고

이는 외적의 정의에 의해서 외적의 결과가 sin0 = sinπ = 0, 즉 크기가 0인 벡터가 되기 때문이다.

 

위 내용을 코드로 만들면

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

struct Coordinate {
    int x;
    int y;
};

int ccw(vector<Coordinate>& cv) {
    return (cv[1].x - cv[0].x) * (cv[2].y - cv[0].y) - (cv[2].x - cv[0].x) * (cv[1].y - cv[0].y); // 벡터 AB와 벡터 BC를 외적했을 때의 z값. 벡터 AB는 점B - 점A로 정의된다.
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    vector<Coordinate> v;
    int n = 3;
    while (n--) {
        Coordinate coord;
        cin >> coord.x >> coord.y;
        v.push_back(coord);
    }

    int result = ccw(v);
    if (result < 0) cout << -1;
    else cout << (result > 0);
    
    return 0;
}