Algorithm - CCW

개념

Counter Clock Wise 알고리즘의 줄임말이다.

세 점의 외적의 성질을 이용하는 알고리즘으로 보통 세점의 방향이 시계, 반시계, 직선인지 판별한다. 또한 외적의 성질을 이용하여 세 점이 이루는 삼각형의 넓이를 알 수 있다.

---

작동원리

CCW

세 점을 크로스 곱하여 그 값이 양수면 반 시계, 0이면 직선, 음수면 시계방향이다.

크로스 곱하여 2로 나누면 세 점이 이루는 삼각형의 크기이다.

---

시간복잡도

세 점을 외적할 때 -> 1

-> O(1)

---

문제

11758 CCW

www.acmicpc.net/problem/11758

11758번: CCW

---

코드

#include <iostream>
using namespace std;

constexpr int COUNTER_CLOCK_WISE = 1;
constexpr int CLOCK_WISE = -1;
constexpr int STRAIGHT = 0;

class Point {
public:
    long long x, y;

    explicit Point(long long x, long long y) : x(x), y(y) {

    }
};

int ccw(Point p1, Point p2, Point p3) {
    long long l = p1.x * p2.y + p2.x * p3.y + p3.x * p1.y;
    long long r = p2.x * p1.y + p3.x * p2.y + p1.x * p3.y;

    if (l - r > 0) {
        return COUNTER_CLOCK_WISE;
    }else if(l - r < 0) {
        return CLOCK_WISE;
    } else {
        return STRAIGHT;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);

    long long x1, x2, x3, y1, y2, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

    cout << ccw(Point(x1, y1), Point(x2, y2), Point(x3, y3)) << "\n";
}