백준 12781번: PIZZA ALVOLOC (C++)

접근

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

12781번: PIZZA ALVOLOC

기하 관련 알고리즘 문제를 풀 때 자주 쓰이는 CCW 알고리즘을 이용한 문제이다. 벡터의 외적을 이용한 문제로, 두개의 벡터를 외적하였을 때 그 방향에 따라 외적 값이 양수인지 음수인지를 확인하여 두 벡터의 관계를 알 수 있다.

1 -> 2 로 가는 벡터와 1 -> 3 으로 가는 벡터를 외적했을 때 1 -> 3 으로 가는 벡터가 1 -> 2 벡터보다 반시계 방향에 있다면 두 벡터의 외적 값은 양수가 나오게 된다. 반대로 반시계 방향에 있으면 음수가 나오게 된다.

따라서 1 -> 2 벡터와 1 -> 3 벡터, 그리고 1 -> 2 벡터와 1 -> 4 벡터를 각각 외적하여 두 외적 값이 서로 반대의 부호를 가진다면 1 -> 2 벡터를 사이에 두고 3번 점과 4번 점은 반대편에 있다는 것을 알 수 있고, 이는 3번과 4번 점을 이으면 1 -> 2 번 벡터와 한 점에서 만난다는 것을 의미한다.

코드

#include <iostream>

using namespace std;

#define endl '\n'

struct INFO {
    int x;
    int y;
};

INFO Info[4];

int ccw(INFO a, INFO b, INFO c) {
    int res = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
    if (res > 0) {
        return 1;
    } else if (res < 0) {
        return -1;
    } else {
        return 0;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 0; i < 4; i++) {
        cin >> Info[i].x >> Info[i].y;
    }

    if (ccw(Info[0], Info[1], Info[2]) * ccw(Info[0], Info[1], Info[3]) < 0) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!