# BOJ 2162번: 선분 그룹

반응형

2차원 평면상에 선분들이 주어질 때, 두 선분이 만나면 같은 그룹이라 한다. 이때 가장 큰 그룹에 속한 선분의 개수를 구하는 문제이다.

그룹핑하기 위해 Union Find를 사용했고, CCW로 선분의 교차 유무를 판별하였다.

 

 

코드는 다음과 같다.

 

#include <cstring>
#include <cstdio>
 
int par[3001];
int L[3001][4];
int maxx(int a, int b) {
    return a > b ? a : b;
}
int minn(int a, int b) {
    return a < b ? a : b;
}
int CCW(double x1, double y1, double x2, double y2, double x3, double y3) {
    double tmp = x1 * y2 + x2 * y3 + x3 * y1;
    tmp -= (y1 * x2 + y2 * x3 + y3 * x1);
    if (tmp < 0)
        return -1;
    if (tmp > 0)
        return 1;
    return 0;
}
int find(int i) {
    if (par[i] < 0)
        return i;
    return par[i] = find(par[i]);
}
void Union(int i, int j) {
    int p = find(i);
    int q = find(j);
    if (p == q)
        return;
    par[p] += par[q];
    par[q] = p;
}
bool isoverlapped(double l1x1, double l1y1, double l1x2, double l1y2, double l2x1, double l2y1, double l2x2, double l2y2) {
    if (maxx(l1x1, l1x2) < minn(l2x1, l2x2))
        return false;
    if (minn(l1x1, l1x2) > maxx(l2x1, l2x2))
        return false;
    if (maxx(l1y1, l1y2) < minn(l2y1, l2y2))
        return false;
    if (minn(l1y1, l1y2) > maxx(l2y1, l2y2))
        return false;
    return true;
}
bool iscrossed(double l1x1, double l1y1, double l1x2, double l1y2, double l2x1, double l2y1, double l2x2, double l2y2) {
    double chk1 = CCW(l1x1, l1y1, l1x2, l1y2, l2x1, l2y1)*CCW(l1x1, l1y1, l1x2, l1y2, l2x2, l2y2);
    double chk2 = CCW(l2x1, l2y1, l2x2, l2y2, l1x1, l1y1)*CCW(l2x1, l2y1, l2x2, l2y2, l1x2, l1y2);
    if (chk1 == 0 && chk2 == 0) {
        return isoverlapped(l1x1, l1y1, l1x2, l1y2, l2x1, l2y1, l2x2, l2y2);
    }
    return chk1 <= 0 && chk2 <= 0;
}
int main()
{
    register int i, j;
    int N;
 
    scanf("%d", &N);
    for (i = 1; i <= N; i++) {
        par[i] = -1;
    }
    for (i = 1; i <= N; i++) {
        scanf("%d %d %d %d", &L[i][0], &L[i][1], &L[i][2], &L[i][3]);
        for (j = 1; j < i; j++) {
            if (iscrossed(L[i][0], L[i][1], L[i][2], L[i][3], L[j][0], L[j][1], L[j][2], L[j][3]) == true) {
                Union(i, j);
            }
        }
    }
    int ans = 0, res=0;
    for (i = 1; i <= N; i++) {
        if (par[i] < 0) {
            ans++;
            res = minn(res, par[i]);
        }
    }
 
    printf("%d\n", ans);
    printf("%d\n", -res);
    return 0;
}