[Algorithm]Baekjoon 2162번 : 선분 그룹

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

2162번: 선분 그룹

 
 
using namespace std;
 
typedef pair<int, int> vector2D;
typedef pair<int, int> point;
typedef pair<point, point> lineSegment;
 
int n, a, b, c, d;
vector<lineSegment> lineSegments;
int parents[3000] = { 0 };
int groupSizes[3000] = { 0 };
 
int FindParent(int node)
{
    if (parents[node] == node) return node;
    return parents[node] = FindParent(parents[node]);
}
 
bool CompareParents(int a, int b)
{
    a = FindParent(a);
    b = FindParent(b);
 
    if (a == b) return true;
    return false;
}
 
void UnionParents(int a, int b)
{
    a = FindParent(a);
    b = FindParent(b);
 
    if (a < b)
    {
        parents[b] = a;
        groupSizes[a] += groupSizes[b];
        groupSizes[b] = 0;
    }
    else
    {
        parents[a] = b;
        groupSizes[b] += groupSizes[a];
        groupSizes[a] = 0;
    }
}
 
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);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b >> c >> d;
 
        lineSegments.push_back({ { a,b }, { c,d } });
        groupSizes[i] = 1;
        parents[i] = i;
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            lineSegment& a = lineSegments[i];
            lineSegment& b = lineSegments[j];
 
            if (IsIntersection(a, b)) // 이어져있고
            {
                if (CompareParents(i, j) == false) // 아직 집합에 안 합쳤으면
                {
                    UnionParents(i, j); // 합친다.
                }
            }
        }
    }
 
    int groupCount = 0;
    int maxGroupSize = 0;
 
    for (int i = 0; i < n; ++i)
    {
        if (groupSizes[i] > 0) ++groupCount;
        maxGroupSize = max(maxGroupSize, groupSizes[i]);
    }
 
    cout << groupCount << endl << maxGroupSize;
}
 
 
 
 
 

 

이전에 풀었던 선분 교차 2에 Union-Find를 결합한 문제이다. 연결된 선분의 그룹의 개수와 최대 그룹의 크기를 구하는 문제이기 때문에 Union-Find를 사용했다. 선분교차에 대한에 특이사항이 추가된건 없기 때문에 그대로 사용하면 된다.