BOJ 12781번 PIZZA ALVOLOC

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

github : https://github.com/junho0956/Algorithm/blob/master/12781/12781/%EC%86%8C%EC%8A%A4.cpp

 

이 문제는 정해진 선인 볼록다각형 위에서 선분의 교차를 판단하는 문제입니다.

삼각형의 면적과 벡터를 이용한 공식을 이용한 CCW 함수를 이용하여 두 선분의 교차를 판별하면 됩니다.

 

 

#include <iostream>
using namespace std;
 
typedef struct {
    int x, y;
}pii;
 
int ccw(pii a, pii b, pii c) {
    int ans = (b.x - a.x) * (c.y - a.y) - (b.y - a.y)* (c.x - a.x);
    if (ans < 0) return 1;
    else if (ans > 0) return -1;
    else return 0;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    pii a, b, c, d;
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
    
    int ans = ccw(a, b, c) * ccw(a, b, d);
    if (ans < 0) cout << "1";
    else cout << "0";
 
    return 0;
}