[백준/C++] 선분 그룹 (No. 2162)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

 

이 문제는 이전에 풀었던 선분 교차 3와 크게 다를게 없는 문제다.

단순히 여기에 union_find가 합쳐진 문제다.

 

먼저 n개의 선분에 대해 선분 a가 다른 선분들과 교차하는지(만나는지) for문으로 체크를 해준다.

 

이때, 선분이 교차하는지 확인은 외적을 이용할 수 있다. 

 

위 그림처럼 선분 a와 b가 교차한다면 외적한 값 v1, v2의 부호가 다름을 알 수 있다.

이때, 하나의 선분을 기준으로 판단을 하면 안된다.

 

왜냐하면 오른쪽 그림처럼 외적 했을 때, a선분을 기준으로는​ 외적 값의 부호가 다르지만 b 선분을 기준으로는 외적 값의 부호가 같은 경우가 있기 때문이다.

 

이렇게 외적을 한 다음 부호를 비교해 두 선분이 교차하는지 확인할 수 있다.

 

+ 두 선분이 교차하는데 외적한 값이 0으로 부호를 비교할 수 없는 경우가 있다.

잘 생각해보면 어떤 경우인지 알 수 있는데 평행한 경우가 이에 해당한다. 

그러므로 이러한 경우를 고려해 평행한 경우 만나는지 체크해 주어야 한다. 

위 그림처러 겹치는 구간의 크기를 비교해 겹치는지 확인을 하고 겹치는 경우 union_find를 통해 a선분과 b선분을 같은 그룹에 있음을 체크해 주면 된다.

 

 

 

 

 

[아이디어 정리]

1. 각 선분에 대해 다른 선분과 교차하는지 확인한다.
2. 두 선분이 교차하는지는 외적을 통해 확인한다.
3. 만약 두 선분이 교차한다면, union_find를 이용해 두 선분을 같은 그룹에 묶는다.
4. 모든 선분에 대해 그룹계산이 끝나면, 그룹의 수를 세고, 가장 많은 선분이 있는 그룹의 선분 수를 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <unordered_map>
using namespace std;

struct line {
	long long x1, x2, y1, y2;
};

int FindPar(int a, vector<int> &par) {
	if (par[a] == a) {
		return a;
	}
	return par[a] = FindPar(par[a], par);
}


long long CCW(pair<long long, long long> a, pair<long long, long long> b) {
	//a, b 벡터의 외적
	return a.first * b.second - a.second * b.first;
}

bool Meet(line a, line b) 
{
	pair<long long, long long> aV, bV;
	aV = make_pair(a.x2 - a.x1, a.y2 - a.y1);
	bV = make_pair(b.x2 - b.x1, b.y2 - b.y1);
	long long ACCW = CCW(aV, make_pair(b.x1 - a.x2, b.y1 - a.y2))* CCW(aV, make_pair(b.x2 - a.x2, b.y2 - a.y2));
	long long BCCW = CCW(bV, make_pair(a.x1 - b.x2, a.y1 - b.y2))* CCW(bV, make_pair(a.x2 - b.x2, a.y2 - b.y2));
	if (ACCW <= 0 && BCCW <= 0) {
		if (ACCW == 0 && BCCW == 0) {
			//한 끝점이 같은 경우도 있다.
			if (a.x1 == a.x2&& b.x2 == b.x1&&a.x2==b.x1) {
				return (min(a.y1, a.y2) <= max(b.y1, b.y2)) && (max(a.y1, a.y2) >= min(b.y1, b.y2));
			}
			return (min(a.x1, a.x2) <= max(b.x1, b.x2)) && (max(a.x1, a.x2) >= min(b.x1, b.x2));
		}
		return true;
	}

	return false;
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	
	vector<int> par(n);
	vector<line> lineV(n);
	for (int i = 0; i < n; i++) {
		par[i] = i;
		cin >> lineV[i].x1 >> lineV[i].y1 >> lineV[i].x2 >> lineV[i].y2;
		for (int j = 0; j < i; j++) {
			if (Meet(lineV[i], lineV[j]))
			{
				int a = FindPar(i, par), b = FindPar(j, par);
				par[b] = min(a, b);
				par[a] = min(a, b);
			}
		}
	}
	set<int> parents;
	vector<int> groups(n,0);
	int maxAns = 0;
	for (int i = 0; i < n; i++) {
		int a = FindPar(i, par);
		parents.insert(a);
		groups[a] += 1;
		maxAns = max(maxAns, groups[a]);
	}
	cout << parents.size() << "\n" << maxAns;

	return 0;
}

 

---

확실히 외적을 이용하니까 이전에 방정식을 이용한 방법보다 깔끔해 보인다.

두 방법이 크게 다르지는 않지만, 좀 더 간단하다는 느낌이 들었다.

중간에 long long 대신 int형을 사용해서 범위를 벗어나 틀리는 오류가 있었다;;

 

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