백준 17387 c++ -선분 교차2 [PlusUltraCode]

[필자 생각 ]

문제를 보고 CCW 알고리즘을 이용해야 된다는 생각이 들었다. 
CCW알고리즘 공식은 알고 있었지만 어떻게 이용해서 선분이 교차되는지 판단하는데는 문제가 있었다.
고등학교 때 배운 선분 교차 방법을 생각해 봤지만 코드로 짜기에는 무척 복잡해졌다. 
몇몇 자료를 찾아보니 다음과 같은 해결책을 찾았다.

[해결]

 

1. 두 선분이 방향과는 상관없이 일단 겹쳐져 있나?

2. 두 선분이 겹쳐진거 상관없이 CCW를 이용하여 일직선이냐 아니냐?

이 두가지 함수를 구하면 된다.

[소스코드]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;



int CCW(long x1, long y1, long x2, long y2, long x3, long y3) {
	//x1 x2 x3 x1
	//y1 y2 y3 y1
	long ccwValue = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
	if (ccwValue == 0)return 0;
	else if (ccwValue < 0)return -1;
	else return 1;
}

bool isOverlab(long x1, long x2, long x3, long x4, long y1, long y2, long y3, long y4) {
	if (min(x1, x2) <= max(x3, x4) && min(x3, x4) <= max(x1, x2) &&
		min(y1, y2) <= max(y3, y4) && min(y3, y4) <= max(y1, y2)) {
		return true;
	}
	return false;
}


bool isCross(long x1,long x2,long x3,long x4,long y1,long y2,long y3,long y4) {
	int abc = CCW(x1, y1, x2, y2, x3, y3);
	int abd = CCW(x1, y1, x2, y2, x4, y4);
	int cda = CCW(x3, y3, x4, y4, x1, y1);
	int cdb = CCW(x3, y3, x4, y4, x2, y2);

	if (abc * abd == 0 && cda * cdb == 0) {
		return isOverlab(x1, x2, x3, x4, y1, y2, y3, y4);
	}
	else if (abc * abd <= 0 && cda * cdb <= 0) {
		return true;
	}
	return false;

}

int main(void) {
	long x1, x2, x3, x4, y1, y2, y3, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	bool cross = isCross(x1,x2,x3,x4,y1,y2,y3,y4);
	if (cross)cout << 1;
	else cout << 0;
}