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

17387번: 선분 교차 2

---

 

문제풀이

 

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

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

 

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

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

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

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

 

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

---

참고자료

CCW(counter clockwise)

선분의 교차 여부 확인

---

코드

cpp

#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();
}