[BAEKJOON] 2162번 선분 그룹

https://www.acmicpc.net/problem/2162

문제조건

1. N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.
   
   
2. 두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 
3. 그룹의 수, 가장 크기가 큰 그룹에 속한 선분의 개수를 구하시오.

접근방법

 

선분끼리 만나는 경우를 하나하나 모두 체크를 해줘야하는지 생각해봤다.

그리고 선분끼리 교차하는 건 코드로 어떻게 나타낼지 감이 안와서 검색을통해 알아냈다.

https://bowbowbow.tistory.com/17

[기하] 외적을 이용해서 선분과 선분의 교차점 구하기

이해하는데 이 블로그글이 정말 많은 도움이 되었다.

이 문제에서는 만나는 점의 정확한정보는 필요없고, 교차하는지만 검증해주면 되고 판별또한 매우쉽다!

1. 주어진 각 좌표를 벡터로 나타내준다.
2. CCW(Counter Clock Wise)를 이용한다.
   1. 외적을 이용한 방향을 판별한다.
   2. 한 선분의 입장에서 다른선분의 두 끝점과 외적을 진행한다.
   3. 두 선분 입장 모두에서 반대 방향이 나오면 두 선분은 교차하는것이다.
3. 평행할 경우에, 겹치는지 판단해준다. 

 

이렇게 선분이 교차하는것에 대한 판별은 끝났고 이제 그룹을 어떻게 형성할지이다.

나는 같은 집합에 속하는지 판단하기 위해서, 가중치가 없이 Kruskal 알고리즘과 유사하게 구현해줬다.

 

소스코드

#include <iostream>
#include <vector>
#define MAX 3001
using namespace std;
typedef long long ll;

int n, parent[MAX], cnt[MAX];
int group, maxNum;
struct info {
	pair<int, int> v1;
	pair<int, int> v2;
};
vector<info> edge;

int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
	ll dir = (x1 * y2 + x2 * y3 + x3 * y1) - (y1 * x2 + y2 * x3 + y3 * x1);
	if (dir < 0) return -1;
	else if (dir > 0) return 1;
	return 0;
}

bool intersect(info e1, info e2) {
	int x1 = e1.v1.first;
	int y1 = e1.v1.second;
	int x2 = e1.v2.first;
	int y2 = e1.v2.second;
	int x3 = e2.v1.first;
	int y3 = e2.v1.second;
	int x4 = e2.v2.first;
	int y4 = e2.v2.second;
	// 두 선분이 평행한 경우
	if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) == 0
		&& ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) == 0) {
		if (e1.v1 > e1.v2) swap(e1.v1, e1.v2);
		if (e2.v1 > e2.v2) swap(e2.v1, e2.v2);
		// 겹치는 경우에 true 반환
		return e1.v1 <= e2.v2 && e2.v1 <= e1.v2;
	}
	// 두 직선 각각의 입장에서 ccw방향이 반대방향이어야 교차
	return ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0
		&& ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0;
}

int find(int num) {
	if (parent[num] == num) return num;
	return parent[num] = find(parent[num]);
}

void merge(int n1, int n2) {
	n1 = find(n1);
	n2 = find(n2);
	if (n1 != n2) {
		parent[n2] = n1;
		cnt[n1] += cnt[n2];
		cnt[n2] = 0;
	}
}

int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		edge.push_back({ {a,b}, {c,d}});
		parent[i] = i;
		cnt[i] = 1;
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if(intersect(edge[i],edge[j])) merge(i + 1,j + 1);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (cnt[i] != 0) {
			group++;
			maxNum = max(maxNum, cnt[i]);
		}
	}

	cout << group << '\n' << maxNum;
}

Unioin-Find + 선분 교차 판정의 문제였다.