선분 교차 판정 알고리즘

선분 L1과 L2가 주어졌을 때, 두 선분이 교차하는지 판정하는 알고리즘.

 

typedef pair<int, int> pii;

pair<pii, pii> L[2];

int func(pair<pii, pii> L1, pair<pii, pii> L2);
int CCW(pii A, pii B, pii C);

int func(pair<pii, pii> L1, pair<pii, pii> L2) {
	pii p1 = L1.first, p2 = L1.second, p3 = L2.first, p4 = L2.second;
	int ccw1 = CCW(p1, p2, p3) * CCW(p1, p2, p4);
	int ccw2 = CCW(p3, p4, p1) * CCW(p3, p4, p2);
	if (ccw1 == 0 && ccw2 == 0) {
		if (p1 > p2) swap(p1, p2);
		if (p3 > p4) swap(p3, p4);
		return (p1 <= p4 && p3 <= p2);
	}
	else return (ccw1 <= 0 && ccw2 <= 0);
}

int CCW(pii A, pii B, pii C) {
	int a = A.first * B.second + B.first * C.second + C.first * A.second;
	int b = B.first * A.second + C.first * B.second + A.first * C.second;
	if (a > b) return 1;
	else if (a == b) return 0;
	else return -1;
}