[백준] 12781 PIZZA ALVOLOC

백준 12781 PIZZA ALVOLOC

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

• 선분과 선분의 교차 (교점 필요 없는 경우) 이용하여 풀이

• 피자의 가장자리의 한 점을 선택할 때, 같은 점을 선택하지 않는다
  -> 두 선분의 교차하는 경우 중 두 선분이 같은 직선 상에 있는 경우와 두 선분의 끝점이 만나는 경우를 고려하지 않아도 된다

#include <iostream>
#include <math.h>
#include <utility>
using namespace std;

int ccw(pair<int, int> a, pair<int, int> b) {
	int cross = a.first * b.second - a.second * b.first;

	if (cross > 0) return 1;
	else if (cross < 0) return -1;
	else return 0;
}

int ccw(pair<int, int> p, pair<int, int> a, pair<int, int> b) {
	a.first -= p.first; a.second -= p.second;
	b.first -= p.first; b.second -= p.second;
	return ccw(a, b);
}

int intersects(pair<int, int> a, pair<int, int> b, pair<int, int> c, pair<int, int> d) {
	int ab = ccw(a, b, c) * ccw(a, b, d);
	int cd = ccw(c, d, a) * ccw(c, d, b);

	return ab < 0 && cd < 0;
}

int main() {
	int x, y;
	cin >> x >> y;
	pair<int, int> a = make_pair(x, y);
	cin >> x >> y;
	pair<int, int> b = make_pair(x, y);
	cin >> x >> y;
	pair<int, int> c = make_pair(x, y);
	cin >> x >> y;
	pair<int, int> d = make_pair(x, y);

	cout << intersects(a, b, c, d);
	return 0;
}