C++[백준]2162번 선분 그룹

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

2162번: 선분 그룹

솔루션

---

선분교차 판정 + 분리집합 으로 해결을 했다.

함수를 구현 할 것이 많아 귀찮은 문제.

 

1) for i 0 to N-1, for j i+1 to N
으로 이중 반복문을 통해서 i번째 입력으로 들어온 선분과 j번째 들어오는 선분이 교차하는지 판별한다.

   - 선분 교차 판정 알고리즘을 이용해 선분이 교차하는지 판단 (선분 교차 2를 참고)

 

2) 선분이 교차한다면, 같은 집합인지 확인한다.

   - UnionFind을 이용하여 같은 집합인지 확인한다. (나동빈씨의 유튜브)

 

3) 같은 집합이 아니라면, 하나의 집합으로 합쳐주고, 갯수도 갱신해 준다.

    - 부모 인덱스를 갱신 할 때, 자식의 선분 그룹 갯수를 부모의 선분 그룹 갯수에 추가한다.

 

 

코드

---

#define ll long long int
#include <iostream>
using namespace std;

struct pa {
	ll x, y;
	struct pa operator-(struct pa t) {
		return { x - t.x,y - t.y };
	}
};

struct Line {
	struct pa pos[2];
};

int parent[3002];
struct Line arr[3002];
int N;
int cnt[3002];
int maxGroup = 1;

int getParent(int x) {
	if (parent[x] == x)return x;
	else return parent[x] = getParent(parent[x]);
}

bool isUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	bool ret = a == b ? true : false;
	
	return ret;
}

void setUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a > b) {
		parent[a] = b;
		cnt[b] += cnt[a];
		maxGroup = max(maxGroup, cnt[b]);
	}
	else {
		parent[b] = a;
		cnt[a] += cnt[b];
		maxGroup = max(maxGroup, cnt[a]);
	}
}

ll ccw2(struct pa p, struct pa q) {
	return p.x * q.y - p.y * q.x;
}

int ccw(struct pa a, struct pa b, struct pa c) {
	ll tmp = ccw2(b - a, c - a);
	if (tmp > 0) return 1;
	else if (tmp == 0) return 0;
	else return -1;
}

bool between(struct pa a, struct pa b, struct pa c) {
	if (ccw(a, b, c) != 0) return false;
	if (a.x != b.x) {
		return (a.x <= c.x && c.x <= b.x) ||
			(a.x >= c.x && c.x >= b.x);
	}
	else return (a.y <= c.y && c.y <= b.y) ||
		(a.y >= c.y && c.y >= b.y);
}

bool isLineIntersection(struct Line a, struct Line b) {
	int std1 = ccw(a.pos[0], a.pos[1], b.pos[0]) * ccw(a.pos[0], a.pos[1], b.pos[1]);
	int std2 = ccw(b.pos[0], b.pos[1], a.pos[0]) * ccw(b.pos[0], b.pos[1], a.pos[1]);

	if (std1 <= 0 && std2 <= 0) {
		if (std1 == 0 && std2 == 0) {
			if(between(a.pos[0],a.pos[1],b.pos[0])||
				between(a.pos[0],a.pos[1],b.pos[1])||
				between(b.pos[0],b.pos[1],a.pos[0])||
				between(b.pos[0], b.pos[1], a.pos[1])) {
				return true;
			}
			else return false;
		}
		return true;
	}
	return false;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].pos[0].x >> arr[i].pos[0].y >> arr[i].pos[1].x >> arr[i].pos[1].y;
		cnt[i] = 1;
		parent[i] = i;
	}
	
	
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			//라인이 겹친다면,
			if (isLineIntersection(arr[i], arr[j])) {
				//같은 그룹이 아니라면,
				if (!isUnion(i, j)) {
					setUnion(i, j);
				}
			}
		}
	}
	bool visit[3002] = { false, };
	int groupCnt = 0;
	for (int i = 0; i < N; i++) {
		int idx = getParent(i);
		if (!visit[idx]) {
			visit[idx] = true;
			groupCnt++;
		}
	}
	cout << groupCnt << "\n" << maxGroup << "\n";
}