[백준] 17387번: 선분 교차 2

📌 문제

https://www.acmicpc.net/problem/17387

📌 설명

CCW 알고리즘을 통해 해결했다.

네 점 A, B, C, D가 있고 선분 AB, 선분 CD의 교차 여부를 판단한다고 할 때, 선분 위의 두 점과 다른 선분의 나머지 한 점의 외적 값을 사용했다. 구체적으로 설명하자면 다음과 같다.

ccw()는 세 점의 외적을 구하는 함수이다. ccw(A, B, C) * ccw(A, B, D) <=0라는 것은 선분 AB를 기준으로 점 C와 점 D가 다른 영역에 존재한다는 것이다. 즉, 교차한다. 그러나 이 조건만으로는 약하므로 선분 CD를 기준으로 점 A와 점 B가 다른 영역에 존재하는지도 확인해야 한다.

추가로 고려해야 할 점은, 모든 ccw 값이 0이라면 두 선분에 포개져있거나 그렇지 않다는 것이다. 따라서 포개져있는지 여부를 확인해주어야 한다. 이는 각 점의 순서를 적절히 바꾸어주고 포개지기 위한 조건을 작성하였다. 이 과정에서 구조체 연산자 오버로딩을 사용하였다.

까다로웠던 점은 ccw의 곱이 매우 커질 수 있기 때문에 long long이 아닌 double형으로 선언되어야 하는 점이었다.

문제를 해결하며 CCW 알고리즘에 대해 알게 되었다. 또한 평소에 구조체를 잘 선언하며 문제를 해결하지 않았는데, 이번 기회를 통해 구조체의 사용과 연산자 오버로딩 설정에 대해 알게 되었다.

📌 코드

#include <iostream>
#include <algorithm>

using namespace std;

struct coor {
	long long x, y;

	bool operator<=(const coor& P)const {
		if (x != P.x)
			return x <= P.x;
		return y <= P.y;
	}
	bool operator>=(const coor& P)const {
		if (x != P.x)
			return x >= P.x;
		return y >= P.y;
	}
};

double ccw(coor A,coor B,coor C) {
	return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

int main() {
	coor A, B, C, D;
	cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y;

	// 선분 AB와 선분 CD에서 A와 C는 각각 B와 D보다 x 또는 y 좌표가 작도록 설정
	if (A >= B) {
		swap(A, B);
	}
	if (C >= D) {
		swap(C, D);
	}

	if (ccw(A, B, C) * ccw(A, B, D) <= 0 && ccw(C, D, A) * ccw(C, D, B) <= 0) {
		if (ccw(A, B, C) * ccw(A, B, D) == 0 && ccw(C, D, A) * ccw(C, D, B) == 0) {
			cout << (A <= D && C <= B);
		}
		else
			cout << 1;
	}
	else
		cout << 0;
}