BOJ 2162 - 선분 그룹

문제 태그 : https://www.acmicpc.net/problem/2162

문제 소개 

만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제

문제 풀이

선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제.
출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다.

선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
struct poi{
    ll x,y;
      bool operator <(const poi &t) const {
        if(x==t.x) return y<t.y;
        return x<t.x;
    }
};
 
ll ccw(poi a,poi m,poi b)
{
    ll t=(a.x-m.x)*(b.y-m.y)-(a.y-m.y)*(b.x-m.x);
    return (t<0)-(t>0);
}struct lin{    poi f,s;};
 
bool cross(lin a,lin b)
{
    if(ccw(a.f,a.s,b.f)*ccw(a.f,a.s,b.s)==0&&ccw(b.f,b.s,a.f)*ccw(b.f,b.s,a.s)==0)
        return !(max(a.f, a.s)<min(b.f,b.s)||max(b.f, b.s)<min(a.f,a.s));
    return ccw(a.f,a.s,b.f)*ccw(a.f,a.s,b.s)<=0&&ccw(b.f,b.s, a.f)*ccw(b.f,b.s,a.s)<=0;
}
 
lin arr[1010101];
ll par[1010101];
ll cnt[1010101];
 
ll fi(ll x){
    if(x==par[x]) return x;
    return par[x]=fi(par[x]);
}
 
void uni(ll a,ll b){
    a=fi(a);
    b=fi(b);
    par[a]=b;
}
 
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld %lld %lld %lld",&arr[i].f.x,&arr[i].f.y,&arr[i].s.x,&arr[i].s.y);
        par[i]=i;
    }
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(cross(arr[i],arr[j])) uni(i,j);
 
    for(i=1;i<=n;i++)
        cnt[fi(i)]++;
 
    ll ans1=0,ans2=0;
    for(i=1;i<=n;i++){
        if(cnt[i]) ans1++;
        ans2=max(ans2,cnt[i]);
    }
 
    printf("%lld %lld",ans1,ans2);
 
    
}