[BOJ] 2162 : 선분 그룹 - travelbeeee

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

---

[알고리즘풀이]

선분이 입력되면 그 전까지 입력된 모든 선분들을 순회하며, 두 선분이 교차하는지 CCW를 이용해서 체크해주고

교차한다면 같은 그룹에 Union-find를 이용해 Union 해준다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int n, P[3000];
int c[3000];

vector<pair<pair<int, int>, pair<int, int>>> point;

int CCW(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
	int temp1 = (b.second - a.second) * (c.first - a.first) + a.second * (b.first - a.first);
	int temp2 = (b.first - a.first) * c.second;

	if (temp1 < temp2) // 반시계
		return 1;
	else if (temp1 > temp2) // 시계
		return -1;
	else // 일직선
		return 0;
}

int isIntersect(pair<int, int> a, pair<int, int> b, pair<int, int> c, pair<int, int> d) {
	int ab = CCW(a, b, c) * CCW(a, b, d);
	int cd = CCW(c, d, a) * CCW(c, d, b);
	if (ab == 0 && cd == 0) {
		if (a > b)swap(a, b);
		if (c > d)swap(c, d);
		return c <= b && a <= d;
	}
	return ab <= 0 && cd <= 0;
}

int find(int x) {
	if (P[x] == x)
		return x;
	return P[x] = find(P[x]);
}

void merge(int x, int y) {
	int P_a = find(x);
	int P_b = find(y);
	P[P_a] = P_b;
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++)
		P[i] = i;

	int z = n;
	int j = 0;
	while (n--) {
		pair<int, int> a, b;
		cin >> a.first >> a.second >> b.first >> b.second;

		for (int i = 0; i < j; i++) {
			pair<int, int> c = point[i].first;
			pair<int, int> d = point[i].second;
			if (isIntersect(a, b, c, d)) {
				merge(i, j);
			}
		}
		point.push_back(make_pair(a, b));
		j++;
	}
	int count = 0;
	for (int i = 0; i < j; i++) {
		if (c[find(i)]++ == 0)
			count++;
	}	
	int m = -1;
	for (int i = 0; i < j; i++) {
		m = max(m , c[i]);
	}
	cout << count << '\n' << m << endl;
}

---