백준: Class 5 - 2162

</br> 클래스 5 플레 문제들도 다 풀자
</br>

2162: 선분 그룹

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

#include <bits/stdc++.h>

using namespace std;

pair<int, int> line[2][3001];
int parent[3001];
int ran[3001];

int f(int u){
    if( parent[u] == u ) return u;
    return parent[u] = f(parent[u]);
}

void merg(int u, int v){
    u = f(u); v = f(v);
    if( u == v ) return;
    if( u > v ) swap(u, v);
    parent[v] = u;
    ran[u] += ran[v];
    ran[v] = 0;
}

int sarea(pair<int, int> &a,
          pair<int, int> &b,
          pair<int, int> &c){
    int x1 = a.first;
    int y1 = a.second;
    int x2 = b.first;
    int y2 = b.second;
    int x3 = c.first;
    int y3 = c.second;
    int ret = x2*y1 + x3*y2 + x1*y3 - (x1*y2 + x2*y3 + x3*y1);
    if( ret < 0 ) return 1;
    if( ret == 0 ) return 0;
    return -1;
}

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

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        int x, y;
        cin >> x >> y;
        line[0][i] = make_pair(x, y);
        cin >> x >> y;
        line[1][i] = make_pair(x, y);
        if( line[0][i] > line[1][i] ) swap(line[0][i], line[1][i]);
        parent[i] = i;
        ran[i] = 1;
    }

    vector<int> v;

    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            int iij = sarea(line[0][i], line[1][i], line[0][j]);
            int iijj = sarea(line[0][i], line[1][i], line[1][j]);
            int jji = sarea(line[0][j], line[1][j], line[0][i]);
            int jjii = sarea(line[0][j], line[1][j], line[1][i]);
            if( iij*iijj <= 0 && jji*jjii <= 0 ){
                if( line[0][i] <= line[1][j] && line[0][j] <= line[1][i] ){
                    merg(i, j);
                }
            }
        }
    }

    int cnt = 0, ans = 0;
    for(int i = 0; i < n; i++){
        if( ran[i] ){
            ans = max(ans, ran[i]);
            cnt++;
        }
    }

    cout << cnt << '\n';
    cout << ans << '\n';

}

클래스 5 첫 플레 문제라 긴장했는데 쉬운 문제라 바로 풀이가 생각나고 그대로 구현해서 한 번에 맞았다 다행
일단 선분 교차 판정(https://cyj893.github.io/algorithm/Algorithm17_15/)이 필요하다
n이 3000이라 3000C2 = 4498500으로 다 해 주면 된다
이제 같은 그룹인 지 확인해야 하므로, 유니온 파인드를 쓰자
merg()는 편하게 번호가 작은 순으로 했고, ran[] 배열에 각 부모가 가진 노드들 수를 저장한다
따라서 마지막에 그룹 개수랑 최댓값 구해주면 끝
</br>

---

이제 두 알고리즘 섞어 쓰고 그런 게 나오는구나
이번 달 바쁘긴 한데 그래도 최대한 많이 풀어야지
</br>