백준 2162 : 선분그룹 (C++)

 

두 선분이 교차한다면 유니온 파인드로 두 선분을 하나의 그룹으로 묶음

 

시간복잡도 : O(n^2) (n=3000)

#include<bits/stdc++.h>
#define MAX 1000000007
#define INF 2000000000
#define MOD 1000000007 
using namespace std;
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

int dt[3] = { -1,0,1 };
/*
int dx[4] = { -1, 0, 0, 1 };
int dy[4] = { 0, -1, 1, 0 };

int dx[8] = { -1, -1, 1, 1, -2, -2, 2, 2 };
int dy[8] = { 2, -2, 2, -2, -1, 1, -1, 1 };
*/
void init() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll ccw(pll a, pll b, pll c) {
    ll k= (a.first - b.first) * (c.second - b.second) - (c.first - b.first) * (a.second - b.second);
    if (k < 0) return -1;
    else if (k == 0) return 0;
    else return 1;
}
int parent[3001];
int getParent(int x) {
    if (x == parent[x])return x;
    else return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a > b)parent[a] = b;
    else parent[b] = a;
}

bool func(pair<pll, pll> a, pair<pll, pll> b) {
    ll x = ccw(a.first, a.second, b.first) * ccw(a.first, a.second, b.second);
    ll y = ccw(b.first, b.second, a.first) * ccw(b.first, b.second, a.second);

    if (x <= 0 && y <= 0) {
        if (x == 0 && y == 0) {
            if (a.first > a.second) swap(a.first, a.second);
            if (b.first > b.second) swap(b.first, b.second);

            return !((b.first > a.second) || (a.first > b.second));
        }
        else return true;
    }
    else return false;
    
}
int main() {
    init();
    int n; cin >> n;
    for (int i = 1; i <= n; i++) parent[i] = i;
    vector<int> cnt(n + 1);
    vector<pair<pll,pll>> v(n + 1);
    for (int i = 1; i <= n; i++) {
        pll x, y;
        cin>>  x.first >> x.second >> y.first >> y.second;
        v[i] = { x,y };
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (func(v[i], v[j])) unionParent(i, j);
        }
    }
    for (int i = 1; i <= n; i++) {
        cnt[getParent(i)]++;
    }
    int c = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] > 0) {
            mx = max(mx, cnt[i]);
            c++;
        }
    }
    cout << c << "\n" << mx << "\n";
}