[Algorithm]Baekjoon 17387번 : 선분 교차 2

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

17387번: 선분 교차 2

 
 
using namespace std;
 
typedef pair<int, int> vector2D;
typedef pair<int, int> point;
typedef pair<point, point> lineSegment;
 
int a, b, c, d;
vector<lineSegment> lineSegments;
 
int CCW(point& s1, point& p1, point& p2)
{
    vector2D v1 = { p1.first - s1.first, p1.second - s1.second };
    vector2D v2 = { p2.first - s1.first, p2.second - s1.second };
 
    long long crossResult = (long long)v1.first * v2.second - (long long)v1.second * v2.first;
 
    if (crossResult < 0) return 1;
    else if (crossResult > 0) return -1;
    return 0;
}
 
bool Compare(point& p1, point& p2)
{
    if (p1.first == p2.first)
    {
        return p1.second <= p2.second;
    }
 
    return p1.first <= p2.first;
}
 
void Swap(point& p1, point& p2)
{
    point temp = p1;
    p1 = p2;
    p2 = temp;
}
 
bool IsIntersection(lineSegment& l1, lineSegment& l2) // 두 선분이 교차하는지 검사.
{
    int ccwResult1 = CCW(l1.first, l2.first, l2.second) * CCW(l1.second, l2.first, l2.second);
    int ccwResult2 = CCW(l2.first, l1.first, l1.second) * CCW(l2.second, l1.first, l1.second);
 
    if (ccwResult1 == 0 && ccwResult2 == 0) // 둘 다 0이면 두 선분이 일단 한 직선위에 존재한다는 것.
    {
        if (Compare(l1.first, l1.second) == false)
        {
            swap(l1.first, l1.second);
        }
 
        if (Compare(l2.first, l2.second) == false)
        {
            swap(l2.first, l2.second);
        }
 
        return Compare(l2.first, l1.second) && Compare(l1.first, l2.second);
    }
 
    return ccwResult1 <= 0 && ccwResult2 <= 0;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    for (int i = 0; i < 2; ++i)
    {
        cin >> a >> b >> c >> d;
        lineSegments.push_back({ { a,b }, { c,d } });
    }
 
    cout << IsIntersection(lineSegments[0], lineSegments[1]);
}
 
 
 
 

 

선분교차1은 완전교차만을 검사했다면, 이번에는 끝점이 이어진것까지 판별해야 한다. 

선분교차1에서 달라진점은, 두 선분이 한직선위에 있는 경우도 검사해야한다는것이다.

 46번째줄부터 59번째 줄까지가 검사하는 코드이다.

 

두 선분에 대한 두개의 ccw값이 전부 0으로 나온다면, 한 직선위에 두개의 선분이 있다는 것이다.

딱 여기까지만 알 수 있다. 한 직선위에 있지만, 이어져있는지 안이어져있는지는 알 수 없다.

그 검사를 하기위해 두 선분에 대해 각각의 min값과 max값을 비교해서 이어져있는지 검사한다.

아마 이전에 비슷한 문제를 풀어본 경험이 있을 수 있는데, y좌표없이 그냥 x축만 있는 환경이라고 가정했을 때, 1~3 선분과 2~4 선분이 겹쳐져 있는지를 위한 검사를 하기위해 아래와 같이 하는 경우가 있다.

 

좌측선분의 maxX(끝지점X값) <= 우측선분의 minX(시작지점X값) && 좌측선분의 minX <= 우측선분의 maxX 

 

위 조건을 만족할 경우, 두 선분은 겹쳐지거나 이어져있다고 판단한다.

만약 끝지점에 이어져있는거는 이어져있다고 판단하지 않는 경우, <=가 아니라 <를 하면 될것이다.

 

바로 이 검사를 적용한 것이다. 다만, 이 문제에서는 y축 좌표도 있다는걸 명심해야한다.

어쨌든 이 검사를 하기위해 먼저 전처리과정을 해야한다. 각 선분은 무작위로 주어지고, 각 선분의 두 점도 정렬되서 주어지는게 아니기 때문에 정렬을 시킨다고 생각하면 된다.

제대로 정렬되어있는지 검사하는 함수가 위 코드의 Compare함수이며, 정렬이 안되어있을 경우 정렬시키기위한 함수가 Swap함수이다.

여기서 말하는 정렬이란, 한 선분의 어떤점이 min값이고 어떤점이 max값인지 정확히 명시해놓는것을 말한다.

그래야 두 선분을 비교하니까..