[C++]백준 - 17387번 문제

17387번: 선분 교차 2 (acmicpc.net)

17387번: 선분 교차 2

 

17387번 : 선분 교차 2

---

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

 

입력

---

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수

 

 

출력

---

L1과 L2가 교차하면 1, 아니면 0을 출력한다.

 

 

---

 

생각해 볼 점

---

CCW 알고리즘을 활용해서 선분이 교차했는지 알아봅니다.

 

CCW 알고리즘은 반시계 방향(Counter-Clock-Wise)의 줄임말로, 세 점이 주어졌을 때

 

세 점이 반시계 방향으로 나아가고 있는 지 확인하는 알고리즘입니다.

 

 

 

점 3개의 방향성을 나타내는 CCW (acmicpc.net)

점 3개의 방향성을 나타내는 CCW

 

더 자세한 내용은 위 링크에서 확인할 수 있습니다. 

 

 

두 선분이 교차하는 지 알려면 CCW 알고리즘을 총 4번 사용해야 합니다.

 

1. CCW(1, 2, 3) * CCW(1, 2, 4)

2. CCW(3, 4, 1) * CCW(3, 4, 2)

 

그리고 1번과 2번 값이 모두 0보다 작아야 선분이 교차합니다.

 

그렇지 않으면, 아래 그림처럼 선분이 교차하지 않습니다.

 

 

 

또한, 아래 그림과 같은 경우 역시 주의해야합니다.

선분 두 개가 평행하지만, 교차하지는 않습니다. 하지만 1~2번 선분이 조금만 더 길었다면 교차할 수도 있습니다.

 

CCW 알고리즘 4개를 구하더라도 모두 0인 경우입니다. 이 경우는 따로 예외처리를 해서,

 

두 선분이 교차하는지 구해야 합니다.

 

코드

---

#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Point;
#define swap(A, B) {Point temp; temp = A; A = B; B = temp;}

//CCW 알고리즘
int ccw(Point A, Point B, Point C)
{
    ll temp1 = A.first * B.second + B.first * C.second + C.first * A.second;
    ll temp2 = A.second * B.first + B.second * C.first + C.second * A.first;
    ll result = temp1 - temp2;
    
    if(result < 0) return -1;
    else if(result == 0) return 0;
    else return 1;
}

//판정
bool is_crossed(Point P1, Point P2, Point P3, Point P4)
{
    int ccw1 = ccw(P1, P2, P3);
    int ccw2 = ccw(P2, P3, P4);
    int ccw3 = ccw(P3, P4, P1);
    int ccw4 = ccw(P4, P1, P2);

    bool is_crossed;
    
    //직선일 때
    if(ccw1 * ccw4 == 0 && ccw2 * ccw3 == 0)
    {
        if(P2 < P1) swap(P1, P2);
        if(P4 < P3) swap(P3, P4);

        //겹쳤으면
        if(P1 <= P4 && P3 <= P2) return true;
        else return false;
    }
    
    return ccw1 * ccw4 <= 0 && ccw2 * ccw3 <= 0;
}

int main() 
{
    Point P1, P2, P3, P4;
    
    cin >> P1.first >> P1.second >> P2.first >> P2.second;
    cin >> P3.first >> P3.second >> P4.first >> P4.second;
    
    if(is_crossed(P1, P2, P3, P4)) cout << 1;
    else cout << 0;
    
	return 0;
}

 

그 외

---