[백준 12781] PIZZA ALVOLOC (C++)

문제 링크: www.acmicpc.net/problem/12781

12781번: PIZZA ALVOLOC

1. 주의할 점

- 선분의 외적을 이용한 CCW에 대해 알고 있어야 한다(1->2->3의 순서로 갈 경우, S가 음수면 시계, 양수면 반시계방향)

- S가 0인 경우를 처리한다

   A: (x1, y1), B: (x2, y2), C: (x3, y3)
-> A: (x1, y1, 1), B: (x2, y2, 1), C: (x3, y3, 1)
-> 벡터 AB: (x2-x1, y2-y1, 0), 벡터 AC: (x3-x1, y3-y1)
-> 2*S = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

 

2. 구현

- 두 선분이 교차할 조건은 3,4번째로 입력 받는 점이 1과 2를 이은 선분을 기준으로 반대편에 위치해야 한다

- 4개의 점을 X[], Y[]배열에 담은 후, 1과 2를 이은 선분에 대해 3번 점과 4번점에 대해 CCW를 구한다

- CCW(1,2,3) * CCW(1,2,4)의 값이 음수라면(서로 반대편에 위치) 1을 출력하고, 아니라면 0을 출력하도록 한다

#include <iostream>
using namespace std;
int x[4], y[4];

int ccw(int a, int b, int c) {
	int da[2] = { y[b] - y[a],x[b] - x[a] };
	int db[2] = { y[c] - y[a],x[c] - x[a] };
	int temp = da[1] * db[0] - da[0] * db[1];
	if (temp < 0) return -1;
	else if(temp>0) return 1;
	else return 0;
}

int main() {
	int dx, dy, result;
	for (int i = 0; i < 4; i++) 
		cin >> x[i] >> y[i];
	result = ccw(0, 1, 2);
	result *= ccw(0, 1, 3);
	(result == -1) ? cout << 1 : cout << 0;
	return 0;
}