[BOJ] 11758 : CCW

문제 링크

11758번: CCW (acmicpc.net)

11758번: CCW

CCW 문제

풀이

 처음에 나는 CCW라는 알고리즘이 있는 줄 모르고 직접 기울기와 방향을 구해서 문제를 해결하려했다. 이건 아닌것같아서 구글링 하다가, 그럼 그렇지 CCW 알고리즘이 있는 걸 알았다.

 CCW란 Counter Clockwise의 줄임말로 점 A,B,C가 주어졌을 때 시계방향으로 놓여있는지, 일직선상에 놓여있는지, 반시계방향으로 놓여있는지 판별해주는 알고리즘이다.

참고 링크

나는 데구리님의 블로그를 참고해서 CCW 알고리즘을 이해했다.

[알고리즘] CCW로 세 점의 방향성 판별하기 (tistory.com)

[알고리즘] CCW로 세 점의 방향성 판별하기

 

공식

두 벡터에 대해서 외적을 하면 다음과 같은 결과가 나온다.

u벡터는 (m1,m2,m3) 이고 v벡터는 (n1,n2,n3) 인데 해당 문제는 2차원이므로 z축 좌표인 m3와 n3는 0이다.

따라서 u x v = (0, 0, m1n2 - m2n1) 이라는 결과를 얻을 수 있다.

u x v 벡터는 z축으로으 방향만 존재하므로 xy평면에 수직이라고 할 수 있다. 데구리님 블로그에 있는 오른손의 법칙에 따라서 D = m1n2 - m2n1 이라고 하면

1. D > 0 일 때는 외적한 벡터가 xy평면에서 z축에 +방향으로 수직(엄지가 위로)이므로 오른손 법칙을 쓰면 반시계방향임을 알 수 있다.

2. D = 0 일 때는 두 벡터가 일직선 위에 존재한다.

3. D < 0 일 때는 외적한 벡터가 xy평면에서 z축에 -방향으로 수직(엄지가 아래로)이므로 오른손 법칙을 쓰면 시계방향임을 알 수 있다.

점 A,B,C 를 각각 A(x1, y1, 0), B(x2, y2, 0), C(x3, y3, 0) 이라고 했을 때

AB벡터는 (x2 - x1, y2 - y1, 0 ) AC벡터는 (x3 - x1, y3 - y1, 0 ) 이라고 할 수 있다.

위에 공식에 대입하기 위해서 x2 - x1 = m1, y2 - y1 = m2 , x3 - x1 = n1, y3 - y1 = n2 라고 하면

D = m1n2 - m2n1 = (x2 - x1)(y3 - y1) - (y2 - y1)(x3 - x1) 으로 바꿀 수 있다.

점 A, B, C 에 대해서 D 값을 구한 다음에 판별식을 적용하면 답을 구할 수 있다.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Priority_queue;
const int INF = INT_MAX;
 
int CCW(pair<int, int> P1, pair<int, int> P2, pair<int, int> P3) {
    return (P2.first - P1.first) * (P3.second - P1.second) - (P3.first - P1.first) * (P2.second - P1.second);
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pair<int, int> P1;
    pair<int, int> P2;
    pair<int, int> P3;
    cin >> P1.first >> P1.second;
    cin >> P2.first >> P2.second;
    cin >> P3.first >> P3.second;
    int D = CCW(P1, P2, P3);
    if (D < 0)
        cout << "-1\n";
    else if (D == 0)
        cout << D << "\n";
    else cout << "1\n";
    return 0;
}

수학을 코딩과 접목하려니까 더 어려운 것같다. 왜 컴공과가 수학을 잘해야한다 하는지 알 것같다.