[C++] 2162번 선분 그룹 - 자료 구조, 기하학, 분리 집합, 선분 교차 판정

1. 문제

• N개의 선분들이 2차원 평면상에 주어져 있다. 두 선분이 서로 만나는 경우에 두 선분은 같은 그룹에 속했다고 하며 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다.
• 이 N개의 선분들은 몇 개의 그룹으로 되어있을까? 또, 가장 큰 그룹에 속하는 선분의 개수는 몇 개인가?

<입력>

• - 1 -   \(N(1 \leq N \leq 3,000)\)
• - N개의 줄 -   선분의 양 끝점의 좌표 \(\left|x_{i} \right|, \left|y_{i} \right| \leq 5,000\)

<출력>

• - 1 -   그룹의 수
• - 2 -   가장 크기가 큰 그룹에 속한 선분의 개수

2. 재정의

• 선분 그룹 개수와 그 크기 구하기

3. 해결 방법

• N*N = 9,000,000으로 CCW를 이용해 선분 교차를 모두 파악하고 이를 union-find로 그룹 짓기

4. 실수한 점, 해결한 점

• X

 

<코드>

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

#define pii pair<int, int>
#define fi first
#define se second

using namespace std;

const int INF = 1187654321;
const int MAX_N = 3001;

// <문제>
// 선분의 개수 N
int N;
// 선분 양 끝점의 좌표
vector<pair<pii, pii>> segment;

// Union-find
int root[MAX_N];
// 그룹에서 원소의 개수
int group_size[MAX_N];
// 그룹의 개수
int groupN;

void input() {
    // 배열 초기화
    for(int i=0; i<MAX_N; i++) {
        root[i] = i;
        group_size[i] = 1;
    }
    
    cin >> N;
    for(int i=0; i<N; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        segment.push_back({{x1, y1}, {x2, y2}});
    }
    groupN = N;
}

// 루트 트리 찾아주는 함수
int rootfind(int x) {
    if(x == root[x])
        return x;
    else
        return root[x] = rootfind(root[x]);
}

// Union-find algorithm
void Union(int x, int y) {
    x = rootfind(x), y = rootfind(y);
    
    if(x == y)
        return;
    
    if(x < y)
        swap(x, y);
        
    root[y] = x;
    group_size[x] += group_size[y];
    groupN--;
}

int CCW(pii p1, pii p2, pii p3) {
    int crossProduct = p1.fi*p2.se + p2.fi*p3.se + p3.fi*p1.se - p1.fi*p3.se - p2.fi*p1.se - p3.fi*p2.se;
    
    if(crossProduct > 0)
        return 1;
    else if(!crossProduct)
        return 0;
    else
        return -1;
}

bool LineSegmenIntersection(pair<pii, pii> x, pair<pii, pii> y) {
    pii p1, p2, p3, p4;
    int ab, cd;
    
    p1 = x.fi, p2 = x.se;
    p3 = y.fi, p4 = y.se;
    
    ab = CCW(p1, p2, p3) * CCW(p1, p2, p4);
    cd = CCW(p3, p4, p1) * CCW(p3, p4, p2);
    
    if(!ab && !cd)
        return (min(y.fi, y.se) <= max(x.fi, x.se)) && (min(x.fi, x.se) <= max(y.fi, y.se));
    return (ab <= 0) && (cd <= 0);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++)
            // i번 간선과 j번 간선이 교차하는 경우 한 그룹으로 묶어주기
            if(LineSegmenIntersection(segment[i], segment[j]))
                Union(i, j);
    
    cout << groupN << '\n';
    cout << *max_element(group_size, group_size + MAX_N);
    
    return 0;
}

 

<왠지 모르겠지만 더 빠른 코드 (풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/11603721

로그인

 

<문제 바로가기>

https://www.acmicpc.net/source/11603721

로그인

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.