2162 선분 그룹 (기하학) [Platinum V]

11758 CCW (기하학) [Gold V]

 

17387 선분 교차 2(기하학) [Gold II]

 

선분 교차2 문제와 굉장히 비슷한 문제입니다. 

여러 선분을 입력으로 받고 겹쳐진 선분들을 하나의 그룹으로 정리,

그룹의 갯수와 가장 많은 선분을 가지고 그룹의 선분 수를 출력 하면 되는 문제입니다.

 

풀이 방법

우선 CCW 공식을 이용하여 모든 선분끼리의 교차 체크를 해야할 것 같습니다.

그리고 Union-Find 알고리즘을 활용하여 그룹을 정의하고, 그룹의 수를 출력, 가장 많은 선분의 수 체크 후 출력 하면

간단하게 해결할 수 있을 것 같습니다. 

 

11758번, 17387번 문제의 연장선 같은 느낌이여서 두 문제를 먼저 풀어보면 좋을 것 같습니다!

 

정답 코드 및 설명

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

struct vertex {
        int x;
        int y;
};

struct edge {
        vertex v1;
        vertex v2;
};

 

정점과 선을 구조체로 정의했습니다. 

 

vector<edge> v;
vector<int> parent;

int CCW(vertex v1, vertex v2, vertex v3);
bool isCross(int id1, int id2);
bool isOverlap(edge e1, edge e2);
void Union(int a, int b);
int find(int a);

선을 입력 받을 vector와 union find를 위한 vector를 만들었고

isCross, isOverlap, CCW 함수를 이용하여 충돌 체크 하였습니다.

이후 Union - Find 함수로 그룹을 정의했습니다.

 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vertex v1 = vertex{ a, b };
        vertex v2 = vertex{ c, d };

        v.push_back({v1, v2});
    }
    parent.resize(N + 1, -1);

    for (int i = 1; i < N; i++) 
    { 
        for (int j = 0; j < i; j++) {
            bool result = isCross(i, j);
            if (result) 
            {
                Union(i, j);
            }
        }
    }

    int groupCount = 0;
    int edgeCount = 0;
    for (int i = 0; i < N; i++)
    {
        if (parent[i] < 0)
        {
            groupCount++;
            edgeCount = min(edgeCount, parent[i]);
        }
    } 

    cout << groupCount << "\n" << -edgeCount << "\n"; 
}

Main 함수 입니다.

 

bool isOverlap(edge e1, edge e2) 
{
        bool isOverlapX = min(e1.v1.x, e1.v2.x) <= max(e2.v1.x, e2.v2.x) && min(e2.v1.x, e2.v2.x) <= max(e1.v1.x, e1.v2.x);
        bool isOverlapY = min(e1.v1.y, e1.v2.y) <= max(e2.v1.y, e2.v2.y) && min(e2.v1.y, e2.v2.y) <= max(e1.v1.y, e1.v2.y);

        return isOverlapX && isOverlapY; 
} 

// (A.x*B.y + B.x*C.y + C.x*A.y) - (A.x*C.y + B.x*A.y + C.x*B.y)   
int CCW(vertex v1, vertex v2, vertex v3)
{
        int result = (v1.x*v2.y + v2.x*v3.y + v3.x*v1.y) - (v1.x*v3.y + v2.x*v1.y + v3.x*v2.y);
        result = std::clamp(result, -1, 1);  
        return result;
} 
 
bool isCross(int id1, int id2)
{
        edge e1 = v[id1];
        edge e2 = v[id2];

        int abc = CCW(e1.v1, e1.v2, e2.v1);
        int abd = CCW(e1.v1, e1.v2, e2.v2);
        int cda = CCW(e2.v1, e2.v2, e1.v1);
        int cdb = CCW(e2.v1, e2.v2, e1.v2); 
         
        if (abc * abd == 0 && cda * cdb == 0) {
                return isOverlap(e1, e2);
        }
        else if (abc * abd <= 0 && cda * cdb <= 0)
        {
                return true;
        }
        return false;
}

교차 체크하는 함수입니다. 

 

void Union(int a, int b)
{
    a = find(a);
    b = find(b);

    if (a == b)
            return;

    parent[a] += parent[b];
    parent[b] = a; 
}
 
int find(int a)
{
    if (parent[a] < 0)
            return a;

    return parent[a] = find(parent[a]);

}

Union - Find 함수로 그룹을 정의하고 있습니다.

parent[a] += parent[b];
parent[b] = a;

Union 함수에서 위 코드는 group 구성 선분의 갯수를 늘려주는 부분입니다.

초기에 -1로 초기화된 것들을 서로 더하여 갯수로 표현하였고

출력 부분에서는 음수 부호를 곱해주어 출력해주고 있습니다.