BOJ 2162. 선분 그룹

🙇‍♀️[Platinum V] 선분 그룹 - 2162

문제 링크

성능 요약

메모리: 2320 KB, 시간: 156 ms

분류

자료 구조, 분리 집합, 기하학, 선분 교차 판정

제출 일자

2024년 3월 9일 21:08:15

문제 설명

N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.

두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 두 선분이 만난다는 것은 선분의 끝점을 스치듯이 만나는 경우도 포함하는 것으로 한다.

N개의 선분들이 주어졌을 때, 이 선분들은 총 몇 개의 그룹으로 되어 있을까? 또, 가장 크기가 큰 그룹에 속한 선분의 개수는 몇 개일까? 이 두 가지를 구하는 프로그램을 작성해 보자.

입력

첫째 줄에 N(1 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나 있다.

출력

첫째 줄에 그룹의 수를, 둘째 줄에 가장 크기가 큰 그룹에 속한 선분의 개수를 출력한다.

먼저 점과 선분을 구조체로 만든다.

struct Point {
	long long x, y;
	bool operator<=(Point const& p1) {
		if (x == p1.x) {
			return y <= p1.y;
		}
		return x <= p1.x;
	}
};

struct Line {
	Point p1, p2;
};

const int INF = 1234567890;
const int MAX = 10000;
// disjoint set 기본 개념
int unf[MAX];
int ch[MAX];

int n;
vector<Line> lines;

유니온 파인드 알고리즘을 짠다.

int Find(int u)
{
	if (u == unf[u])
		return u;

	return unf[u] = Find(unf[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;
	unf[v] = u;
}

CCW 알고리즘은 다음과 같다.

long long CCW(const Point& p1, const Point& p2, const Point& p3)
{
	long long res = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

	// 행렬식을 통해서 구하기
	// int determinant = (p2.x*p3.y - p2.y*p3.x) - \
    //                   (p1.x*p3.y - p1.y*p3.x) + \
    //                   (p1.x*p2.y - p1.y*p2.x);

	if (res > 0)
		return 1;   //반시계
	else if (res < 0)
		return -1;     //시계
	else return 0;
}

bool isCross(Line& l1, Line& l2)
{
	long long std1, std2;

	std1 = CCW(l1.p1, l1.p2, l2.p1) * CCW(l1.p1, l1.p2, l2.p2);
	std2 = CCW(l2.p1, l2.p2, l1.p1) * CCW(l2.p1, l2.p2, l1.p2);

	if (std1 <= 0 && std2 <= 0) {
		if (std1 == 0 && std2 == 0) {     //선분이 일직선인 경우
			if (l1.p2 <= l1.p1) swap(l1.p1, l1.p2);
			if (l2.p2 <= l2.p1) swap(l2.p1, l2.p2);

			return l1.p1 <= l2.p2 && l2.p1 <= l1.p2;
		}
		else return true;   //일직선이 아니면 교차함
	}
	else return false;  //CCW가 같은 방향이 있으면 
}

각 선분을 그리면서 곂치는 부분이 생기면 그룹으로 만든다.

unf배열에 기록하고 ch배열에 그룹의 개수를 저장한다.

void solve()
{
	cin >> n;
	lines = vector<Line>(n + 1);

	long long x1, x2, y1, y2;
	for (int i = 1; i <= n; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		lines[i].p1 = { x1, y1 };
		lines[i].p2 = { x2, y2 };
		// 처음은 자기 자신이 그룹의 대장.
		unf[i] = i;
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (i == j)
				continue;

			if (isCross(lines[i], lines[j]))
			{
				// 교차할 경우 그룹에 추가
				Merge(i, j);
			}
		}
	}

	int cnt = 0, maxCnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		ch[Find(i)]++;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (ch[i] == 0)
			continue;

		cnt++;
		maxCnt = max(maxCnt, ch[i]);
	}

	//for (int i = 1; i <= n; ++i)
	//{
	//	cout << unf[i] << " ";
	//}
	//cout << endl;
	//for (int i = 1; i <= n; ++i)
	//{
	//	cout << ch[i] << " ";
	//}
	//cout << endl;

	cout << cnt << '\n';
	cout << maxCnt << '\n';
}

6
1 0 3 0
1 1 3 1
3 1 2 3
2 3 1 1
0 2 2 4
2 0 0 3

이런 예시가 있을 때 최종적으로 unf와 ch배열을 다음과 같이 나온다.

🚀풀이

Union & Find와 CCW 알고리즘을 섞은 문제였다.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

struct Point {
	long long x, y;
	bool operator<=(Point const& p1) {
		if (x == p1.x) {
			return y <= p1.y;
		}
		return x <= p1.x;
	}
};

struct Line {
	Point p1, p2;
};

const int INF = 1234567890;
const int MAX = 10000;
// disjoint set 기본 개념
int unf[MAX];
int ch[MAX];

int n;
vector<Line> lines;

int Find(int u)
{
	if (u == unf[u])
		return u;

	return unf[u] = Find(unf[u]);
}

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;
	unf[v] = u;
}

long long CCW(const Point& p1, const Point& p2, const Point& p3)
{
	long long res = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);

	// 행렬식을 통해서 구하기
	// int determinant = (p2.x*p3.y - p2.y*p3.x) - \
    //                   (p1.x*p3.y - p1.y*p3.x) + \
    //                   (p1.x*p2.y - p1.y*p2.x);

	if (res > 0)
		return 1;   //반시계
	else if (res < 0)
		return -1;     //시계
	else return 0;
}

bool isCross(Line& l1, Line& l2)
{
	long long std1, std2;

	std1 = CCW(l1.p1, l1.p2, l2.p1) * CCW(l1.p1, l1.p2, l2.p2);
	std2 = CCW(l2.p1, l2.p2, l1.p1) * CCW(l2.p1, l2.p2, l1.p2);

	if (std1 <= 0 && std2 <= 0) {
		if (std1 == 0 && std2 == 0) {     //선분이 일직선인 경우
			if (l1.p2 <= l1.p1) swap(l1.p1, l1.p2);
			if (l2.p2 <= l2.p1) swap(l2.p1, l2.p2);

			return l1.p1 <= l2.p2 && l2.p1 <= l1.p2;
		}
		else return true;   //일직선이 아니면 교차함
	}
	else return false;  //CCW가 같은 방향이 있으면 
}

void solve()
{
	cin >> n;
	lines = vector<Line>(n + 1);

	long long x1, x2, y1, y2;
	for (int i = 1; i <= n; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		lines[i].p1 = { x1, y1 };
		lines[i].p2 = { x2, y2 };
		// 처음은 자기 자신이 그룹의 대장.
		unf[i] = i;
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (i == j)
				continue;

			if (isCross(lines[i], lines[j]))
			{
				// 교차할 경우 그룹에 추가
				Merge(i, j);
			}
		}
	}

	int cnt = 0, maxCnt = 0;
	for (int i = 1; i <= n; ++i)
	{
		ch[Find(i)]++;
	}

	for (int i = 1; i <= n; ++i)
	{
		if (ch[i] == 0)
			continue;

		cnt++;
		maxCnt = max(maxCnt, ch[i]);
	}

	//for (int i = 1; i <= n; ++i)
	//{
	//	cout << unf[i] << " ";
	//}
	//cout << endl;
	//for (int i = 1; i <= n; ++i)
	//{
	//	cout << ch[i] << " ";
	//}
	//cout << endl;

	cout << cnt << '\n';
	cout << maxCnt << '\n';
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}