[BOJ] 2162 선분 그룹

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

 

 

문제 풀이:

1. 두 선분을 뽑아 만나는지 확인한다
   • 선분1에서 선분2의 한 점과의 ccw, 다른 점과의 ccw가 둘 다 0이고 반대의 경우도 다 0이면 두 선분이 일직선 상에 존재한다는 말이므로 따로 if문을 만들어서 겹치는지 확인해준다
   • 다 0이 아니라면 선분1에서 선분2로의 ccw곱이 음수이고, 선분2에서 선분1로의 ccw곱도 음수이면 둘은 겹친다고 볼 수 있다.
2. 겹친다면 union find 알고리즘을 이용해서 연결 시켜준다.
   • 각 그룹에 속하는 선분의 개수를 알기 위해 루트에 새로운 선분 그룹을 연결할 때, 그 인원수를 루트 부모 변수에 더해준다. 
   • 즉, 부모를 기록하는 변수인 p를 처음에 -1로 초기화하고 다른 선분이 추가되면 -2, -3, ... 이런 식으로 음수방향으로 증가시킨다.
   • 이미 그룹인 것이 다른 그룹과 합쳐지는 것일 수 있으므로 p[x] += p[y] 이런식으로 연산해주자
3. 가장 크기가 큰 그룹에 속한 선분의 개수를 알기 위해 마지막에 포문을 돌려 p[i] 값을 보면서 가장 값이 작은 것을 찾아 -1를 곱해주자
4. 그룹의 개수는 맨 처음 n개로 시작해서 그룹이 합쳐질 때마다 1씩 감소해줘서 마지막에 남는 수가 그룹의 개수가 된다.

 

 

 

소스 코드:

typedef pair<double,double> P;
typedef pair<P,P> PP;
vector<PP> v;
int cnt[3001],p[3001],tmp;
int res;
P Pccw1, Pccw2;

int find(int x) {
	if (p[x] < 0) return x;

	return p[x] = find(p[x]);
}
bool merge(int x, int y) {
	x = find(x);
	y = find(y);

	if (x != y) {
		p[x] += p[y];
		p[y] = x;
		return true;
	}
	return false;
}

P doccw(PP a, PP b);

bool func(PP a, PP b) {
	Pccw1 = doccw(a, b);
	Pccw2 = doccw(b, a);
	if (Pccw1.first == 0 && Pccw1.second == 0 && Pccw2.first == 0 && Pccw2.second==0) {
		P a1 = a.first, a2 = a.second;
		P b1 = b.first, b2 = b.second;
		if (min(a1.first, a2.first) > max(b1.first, b2.first)
			|| min(b1.first, b2.first) > max(a1.first, a2.first)) return false;
		else if (min(a1.second, a2.second) > max(b1.second, b2.second)
			|| min(b1.second, b2.second) > max(a1.second, a2.second)) return false;
	}
	if (Pccw1.first*Pccw1.second<=0&& Pccw2.first*Pccw2.second <= 0) return true;

	return false;
}
P doccw(PP a, PP b) {
	P a1 = a.first, a2 = a.second;
	P b1 = b.first, b2 = b.second;

	double ccw11 = (a1.first*a2.second + a2.first*b1.second + b1.first*a1.second)
		- (a2.first*a1.second + b1.first*a2.second + a1.first*b1.second);
	double ccw22 = (a1.first*a2.second + a2.first*b2.second + b2.first*a1.second)
		- (a2.first*a1.second + b2.first*a2.second + a1.first*b2.second);

	return make_pair(ccw11, ccw22);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	for(int i=0;i<n;i++){
		double q, w, e, r;
		cin >> q >> w >> e >> r;
		v.push_back({ {q,w},{e,r} });
	}
	fill(p, p + 3000, -1);
	int t = n;
	int len = v.size();
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			if (func(v[i], v[j])) {
				if (merge(i, j)) {
					t--;
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		res = min(res, p[i]);
	}
	cout << t << "\n"<< res*(-1) << '\n';
	return 0;
}