[Algorithm]Baekjoon 17386번 : 선분 교차 1

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

17386번: 선분 교차 1

 

 
 
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);
 
    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]);
}
 
 
 
 
 

 

CCW알고리즘을 이용한 선분교차 여부를 검사하는 문제이다. 

선분교차알고리즘은 기하알고리즘 중에서는 꽤나 자주나오는 알고리즘이다.

두 선분의 각 점 4개를 이용해서 판별하는데, 한 선분의 한 점을 기준으로 다른선분의 두개의 점에 대해 방향벡터를 먼저 만든다음 각 벡터들끼리의 시계방향인지, 반시계방향인지를 따져서 선분교차를 판별한다.

 

자세한설명은 다른사람들이 잘 설명해놔서.. 뭔가 어려운 알고리즘같아 보이더라도, 그냥 외적의 성질을 알고있으면 이해하는데 전혀 어렵지 않다.

 

선분 두개만 주어지는데 굳이 벡터에 넣어서 하는 이유는, 사실 선분그룹이라는 다른 문제를 풀다가 뭔가 검증하려고 이 문제를 풀어서 그렇다.