2162. 선분 그룹

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

2162번: 선분 그룹

문제 설명

선분의 양끝의 점 2개를 N번 입력받고 선분끼리 만나면 선분 그룹안에 속한다고 한다.

이 때, 선분 그룹의 갯수와 크기가 가장 큰 그룹의 선분 갯수를 출력하면 된다.

 

여기서 필요한 것은 두 선분이 만나는 것을 체크하는 것과 그룹을 만드는 것이다.

두 선분이 만나는지 아닌지를 판단하는 CCW와 그룹을 만드는 Disjoint-Set을 사용했다.

 

평소에 Disjoint-Set을 구현할 때 rank를 잘 사용하지 않지만 이번에는 그룹에 속한 선분의 갯수를 구하기 위해서 rank 배열을 사용했다. 별로 쓸모 없을 줄 알았는데 생각보다 유용한 것 같다.

 

시간 복잡도는 \( O(N^2log^*N) \)  으로 서로다른 두 선분\((O(N^2))\)을 CCW로 판단하여 선분이 교차하면 merge\( (O(log^*N)) \) 를 한다.

 

 

#include <bits/stdc++.h>
 
using namespace std;
 
#define endl '\n'
#define int long long
 
using pii = pair<int, int>;
 
const double EPS = 1e-9;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
class DisjointSet
{
public:
    vector<int> parent, rank;
    DisjointSet(){}
    DisjointSet(int size)
    {
        parent.resize(size+1, 0);
        rank.resize(size+1, 1);
        for(size_t i=0;i<parent.size();i++)
            parent[i] = i;
    }
    int find(int v)
    {
        if(parent[v] == v) return v;
        return parent[v] = find(parent[v]);
    }
    bool merge(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return false;
        if(rank[v] >= rank[u])
        {
            parent[u] = v;
            rank[v] += rank[u];
        }
        else
        {
            parent[v] = u;
            rank[u] += rank[v];
        }
        return true;
    }
};
 
int ccw(pii a, pii b, pii c)
{
    int ans = (a.first * b.second + b.first * c.second + c.first * a.second) - (a.second * b.first + b.second * c.first + c.second * a.first);
    if(ans > 0) return 1;
    else if(ans < 0) return -1;
    return 0;    
}
 
bool check(pii a, pii b, pii c, pii d)
{
    int abc = ccw(a, b, c);
    int abd = ccw(a, b, d);
    int cda = ccw(c, d, a);
    int cdb = ccw(c, d, b);
    if(abc * abd == 0 && cda * cdb == 0)
    {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);
        return a <= d && c <= b;
    }
    return abc * abd <= 0 && cda * cdb <= 0;
}
 
int32_t main()
{
    cin.sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    DisjointSet DS(n);
    vector<pair<pii, pii>> v(n);
    for(int i=0;i<n;i++)
    {
        cin >> v[i].first.first >> v[i].first.second >> v[i].second.first >> v[i].second.second;
    }
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(check(v[i].first, v[i].second, v[j].first, v[j].second))
            {
                DS.merge(i, j);
            }
        }
    }
    int num = 0, mx = 0;
    for(int i=0;i<n;i++)
    {
        if(DS.find(i) == i)
        {
            num++;
            mx = max(mx, DS.rank[i]);
        }
    }
 
    cout << num << endl << mx;
 
    return 0;
}