[BOJ] 선분 그룹

[BOJ] 선분 그룹

Problem URL : 선분 그룹

#include <iostream>
#include <algorithm>
#define p pair<int,int>
#define line pair<p,p>
using namespace std;

int n, group[3001], cnt[3001];
line lines[3001];

int ccw(p a, p b, p c) {
    int r = a.first * b.second + b.first * c.second + c.first * a.second;
    r -= a.second * b.first + b.second * c.first + c.second * a.first;
    if (r > 0) return 1;
    if (r < 0) return -1;
    return 0;
}

int iscross(p a, p b, p c, p d) {
    int r1 = ccw(a, b, c) * ccw(a, b, d);
    int r2 = ccw(c, d, a) * ccw(c, d, b);
    if (r1 == 0 && r2 == 0) {
        return !(max(a, b) < min(c, d) || max(c, d) < min(a, b));
    }
    return r1 <= 0 && r2 <= 0;
}

int find(int u) {
    if (u == group[u]) return u;
    return group[u] = find(group[u]);
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u > v) swap(u, v);
    group[u] = v;
    cnt[v] += cnt[u];
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> lines[i].first.first >> lines[i].first.second >> lines[i].second.first >> lines[i].second.second;
        group[i] = i;
        cnt[i] = 1;
    }

    int groupNum = n;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (iscross(lines[i].first, lines[i].second, lines[j].first, lines[j].second)) {
                int u = find(i), v = find(j);
                if (u != v) {
                    merge(u, v);
                    groupNum--;
                }
            }
        }
    }
    
    int maxCnt = 0;
    for (int i = 1; i <= n; i++) {
        maxCnt = max(maxCnt, cnt[i]);
    }

    cout << groupNum << endl << maxCnt;

    return 0;
}

Comments

CCW와 선분 교차 관련 알고리즘은 링크를 참조하자