[BOJ] 2162 : 선분 그룹

#include <bits/stdc++.h>
#define fst first
#define snd second
using namespace std;
typedef pair<int, int> pi;

int n, par[3003], cnt[3003];
pi p[6003];

int ccw(pi a, pi b, pi c) {
    int r = a.fst*b.snd + b.fst*c.snd + c.fst*a.snd;
    r -= a.snd*b.fst + b.snd*c.fst + c.snd*a.fst;
    if (r > 0) return 1;
    if (r < 0) return -1;
    return 0;
}

int iscross(pi a, pi b, pi c, pi d) {
    int r1 = ccw(a,b,c)*ccw(a,b,d);
    int r2 = ccw(c,d,a)*ccw(c,d,b);
    if (!r1 && !r2) {
        if (a > b) swap(a, b);
        if (c > d) swap(c, d);
        return c<=b && a<=d;
    }
    return r1<=0 && r2<=0;
}

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

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

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n*2; i++) {
        scanf("%d %d", &p[i].fst, &p[i].snd);
        par[i/2] = i/2;
        cnt[i/2] = 1;
    }

    int dap1 = 0, dap2 = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            if (iscross(p[i*2-1],p[i*2],p[j*2-1],p[j*2])) {
                int u = find(i), v = find(j);
                if (u != v) {
                    merge(u, v);
                    dap1++;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        dap2 = max(dap2, cnt[i]);
    }

    printf("%d\n%d\n", n-dap1, dap2);

    return 0;
}