선분 교차 (Platinum V)

union find와 선분 교차를 섞어 놓아 플래티넘으로 연성한 이상한?문제이다

난이도 기여에 있던 댓글 중 하나가 눈에 띄었다: union find에 선분 교차를 싸 먹어 드시겠습니까?

다음은 내가 푼 코드이다

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
ll N, par[3001], rankk[3001], num[3001], res, maxx;
pii v1, v2;
vector<pair<pii, pii> > l;
pair<ll, ll> t1,t2, t3, t4;
ll ccw(pair<ll, ll> p1, pair<ll, ll> p2, pair<ll, ll> p3){
	ll s=p1.first*p2.second+p2.first*p3.second+p3.first*p1.second;
	s-=p2.first*p1.second+p3.first*p2.second+p1.first*p3.second;
	if(s>0) return 1;
	else if(s<0) return -1;
	else return 0;
}// CCW with cross product)
bool intersect(pair<pii, pii> l1, pair<pii, pii> l2){
	if(l1>l2) swap(l1, l2);
	pair<ll, ll> c1=l1.first;
	pair<ll, ll> c2=l1.second;
	pair<ll, ll> c3=l2.first;
	pair<ll, ll> c4=l2.second;
	ll a=ccw(c1, c2, c3)*ccw(c1, c2, c4);
	ll b=ccw(c3, c4, c1)*ccw(c3, c4, c2);
	if(a==0 and b==0){
		if(c1>c2) swap(c1, c2);
		if(c3>c4) swap(c3, c4); 
		if(c2>=c3 and c4>=c1) return true;
		else return false;
	}
	else if(a<=0 and b<=0) return true;
	else return false;
}
void init(ll n){
	for(ll i=1;i<=n;i++) par[i]=i, rankk[i]=1;
}
ll find(ll n){
	if(par[n]==n) return n;
	else return par[n]=find(par[n]);
}
void merge(ll a, ll b){
	a=find(a), b=find(b);
	if(a==b) return;
	if(rankk[a]>rankk[b]) swap(a, b);
	par[a]=b;
	if(rankk[a]==rankk[b]) rankk[b]++;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N;
	init(N); // 초기화 
	for(int i=1;i<=N;i++){
		cin >> v1.first >> v1.second >> v2.first >> v2.second;
		l.push_back(make_pair(v1, v2));
	}
	for(int k=1;k<=2;k++){
		for(ll i=0;i<l.size();i++){
			for(ll j=0;j<l.size();j++){
				if(intersect(l[i], l[j])==true){
					merge(i+1, j+1);
				}
			}
		}	
	}
	for(ll i=1;i<=N;i++) num[par[i]]++;
	for(ll i=1;i<=N;i++){
		if(num[i]!=0){
			if(num[i]>maxx) maxx=num[i];
			res++;
		}
	} 
	cout << res << '\n' << maxx;
}

푸는 데에 있어서 두 번 정도 틀려먹었다. 왜일까? 

답은 처음부터 멍청하게 완전히 merge될 것이라 착각한 것이다.

착각하지 마라 인간. 한 번 더 merge 해 주어야지 루트로 합쳐진다

근데 진짜 문제가 약간 뭐랄까

이상한 거 두 개 묶어 놓은 느낌이라 수상하다