[BOJ/백준] 2162 - 선분 그룹

2162번: 선분 그룹

---

CCW

 

+

 

Union Find ALG

---

---

• 제목

선분 그룹

---

• 조건

시간 제한 : 2 초

메모리 제한 : 128 MB 

---

• 문제

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

---

• 입력

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

---

• 출력

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

---

예제 입력1	예제 출력1
3 1 1 2 3 2 1 0 0 1 0 1 1	1 3

예제 입력2	예제 출력2
3 -1 -1 1 1 -2 -2 2 2 0 1 -1 0	2 2

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
#define endl '\n'

#define pii pair<int, int>
#define vppp vector<pair<pii, pii>>

int root[3000];
int rootCheck[3000];
vppp vt;

int find_root(int x){
	if(root[x] == x) return x;
	return root[x] = find_root(root[x]);
}

void union_root(int x, int y){
	x = find_root(x);
	y = find_root(y);
	if(x != y) root[x] = y;
}

void init(int l){
	for(int n = 0 ; n < l ; n++){
		root[n] = n;
		rootCheck[n] = 0;
	}
}

int ccw(pii a, pii b, pii c){
	int tmp = (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
	if(tmp > 0) return 1;
	else if(tmp < 0) return -1;
	else return 0;
}

bool isMeet(int a, int b){
	int ccw1 = ccw(vt[a].first, vt[a].second, vt[b].first) * ccw(vt[a].first, vt[a].second, vt[b].second);
	int ccw2 = ccw(vt[b].first, vt[b].second, vt[a].first) * ccw(vt[b].first, vt[b].second, vt[a].second);
	if(ccw1 <= 0 && ccw2 <= 0){
		if(ccw1 == 0 && ccw2 == 0){
			if(vt[a].first > vt[a].second) swap(vt[a].first, vt[a].second);
			if(vt[b].first > vt[b].second) swap(vt[b].first, vt[b].second);
			return vt[a].first <= vt[b].second && vt[b].first <= vt[a].second;
		}
		return true;
	}
	return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int sz;
    int x1, x2, y1, y2;
    cin >> sz;
    init(sz);
    for(int n = 0 ; n < sz ; n++){
    	cin >> x1 >> y1 >> x2 >> y2;
    	vt.push_back({{x1, y1},{x2, y2}});
	}
	for(int n = 0 ; n < sz ; n++){
		for(int m = n + 1 ; m < sz ; m++){
			if(isMeet(n, m)){
				if(find_root(n) != find_root(m)) union_root(n, m);
			}
		}
	}
	for(int n = 0 ; n < sz ; n++) rootCheck[find_root(root[n])]++;
	int maxRoot = 0, cntRoot = 0;
	for(int n = 0 ; n < sz ; n++){
		maxRoot = max(maxRoot, rootCheck[n]);
		if(rootCheck[n] != 0) cntRoot++;
	}
	cout << cntRoot << endl << maxRoot << endl;
    return 0;
}