[백준 C++] 17387 선분 교차 2 - 많은조건분기

17387번: 선분 교차 2

---

 

문제풀이

 

기하학 & 많은 조건 분기 유형의 문제입니다.

두 선분이 교차하는 세 가지 경우를 체크해서 풀었습니다.

 

1. (양쪽 선분 모두) 현재 선분을 기준으로 상대 선분의 두 점이 좌우 양쪽에 위치하는 경우

2. 상대 선분의 한 점이 현재 선분을 기준으로 동일선상에 위치하고 상대 선분은 1번 조건에 해당하는 경우

3. (양쪽 선분 모두) 상대 선분의 한 점이 현재 선분을 기준으로 동일선상에 위치하는 경우

3-a. 두 선분이 같은 일직선 상에 존재하므로 네 점의 좌표 비교를 통해 두 선분이 겹치는지 판별

 

이 경우들을 두 벡터의 외적을 통해 값을 구하는 CCW 알고리즘을 이용해서 판별하도록 구현했습니다.

---

참고자료

CCW(counter clockwise)

선분의 교차 여부 확인

---

코드

#include <iostream>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> point;

ll X1, Y1, X2, Y2, X3, Y3, X4, Y4;
point P1, P2, P3, P4;

ll CCW(point A, point B, point C)
{
	ll Result = (B.first - A.first) * (C.second - A.second);
	Result -= (C.first - A.first) * (B.second - A.second);
	
	if (Result > 0)
	{
		return 1;
	}
	else if (Result < 0)
	{
		return -1;
	}

	return 0;
}

bool Intersect()
{
	ll C1 = CCW(P1, P2, P3);
	ll C2 = CCW(P1, P2, P4);
	ll C3 = CCW(P3, P4, P1);
	ll C4 = CCW(P3, P4, P2);

	ll Con1 = C1 * C2;
	ll Con2 = C3 * C4;

	if (Con1 < 0 && Con2 < 0)
	{
		return true;
	}
	else if ((Con1 == 0 && Con2 < 0)
			|| (Con1 < 0 && Con2 == 0)
			|| ((Con1 == 0 && Con2 == 0) && (C1 != 0 || C2 != 0) && (C3 != 0 || C4 != 0)))
	{
		return true;
	}
	else if (C1 == 0 && C2 == 0 && C3 == 0 && C4 == 0)
	{
		if (X1 == X2)
		{
			if (Y1 < Y2 && Y3 < Y4
				&& Y3 <= Y2 && Y1 <= Y4)
			{
				return true;
			}
			else if (Y1 < Y2 && Y3 > Y4
				&& Y4 <= Y2 && Y1 <= Y3)
			{
				return true;
			}
			else if (Y1 > Y2 && Y3 < Y4
				&& Y3 <= Y1 && Y2 <= Y4)
			{
				return true;
			}
			else if (Y1 > Y2 && Y3 > Y4
				&& Y4 <= Y1 && Y2 <= Y3)
			{
				return true;
			}
		}
		else if (X1 < X2 && X3 < X4
				&& X3 <= X2 && X1 <= X4)
		{
			return true;
		}
		else if (X1 < X2 && X3 > X4
				&& X4 <= X2 && X1 <= X3)
		{
			return true;
		}
		else if (X1 > X2 && X3 < X4
				&& X3 <= X1 && X2 <= X4)
		{
			return true;
		}
		else if (X1 > X2 && X3 > X4
				&& X4 <= X1 && X2 <= X3)
		{
			return true;
		}
	}

	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> X1 >> Y1 >> X2 >> Y2;
	cin >> X3 >> Y3 >> X4 >> Y4;

	P1.first = X1;
	P1.second = Y1;
	P2.first = X2;
	P2.second = Y2;

	P3.first = X3;
	P3.second = Y3;
	P4.first = X4;
	P4.second = Y4;

	cout << Intersect();
}