백준 12781 PIZZA ALVOLOC C++

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

12781번: PIZZA ALVOLOC

피자가 어떤 모양으로 주어질 지는 모르지만 볼록 다각형이라는 힌트가 있습니다.

이 때 가장자리에 4개의 점을 찍었을 때 4조각으로 나뉘는 지 판단하는 문제입니다.

피자 모양과 상관없이 4개의 점을 기준으로 4조각으로 나누려면 두 선분이 교차하면 됩니다.

단 이 때 교차의 조건으로 한 점이 다른 선분 위에 있으면 안 됩니다. 

 

위 조건을 만족시키려면 CCW를 계산하였을 때 하나는 시계, 하나는 반시계 방향을 만족하면 됩니다.

단 일반적인 CCW의 경우, 하나가 시계, 하나가 반시계여도 두 선분이 떨어져 있을 수 있지만, 문제의 조건으로 볼록다각형이 주어져 있으므로, 그러한 케이스가 발생할 수 없습니다.

 

따라서 단순히 CCW 계산 후 시계, 반시계가 하나 씩 있는 지 판단하면 됩니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <algorithm>

using namespace std;

// 볼록 다각형이므로 CCW 시계, 반시계 하나씩 나오는데 정답 아닌 경우 없음 

pair<int, int> p1, p2, p3, p4;

void init()
{
    p1 = {0, 0}; p2 = {0, 0}; p3 = {0, 0}; p4 = {0, 0};
    cin >> p1.first >> p1.second;
    cin >> p2.first >> p2.second;
    cin >> p3.first >> p3.second;
    cin >> p4.first >> p4.second;
}

int CCW(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
    // a->b->c 시계 방향 -1, 일직선 0, 반시계 방향 1 
    int s = a.first * b.second + b.first * c.second + c.first * a.second;
    s -= (a.second * b.first + b.second * c.first + c.second * a.first);
    
    if(s > 0)
        return 1;
    else if(s == 0)
        return 0;
    else 
        return -1;
}

void calc()
{
    int s1 = CCW(p1, p2, p3);
    int s2 = CCW(p1, p2, p4);
    
    int res = s1 * s2;
    cout << (res < 0);
}

int main()
{
    init();
    calc();
}