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

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
 
int N = 0;
int group = 0; 
int seg = 0;
bool visit[3001] = {};
int parent[3001] = {};
std::vector<int> graph[3001] = {};
std::vector<std::pair<int, int>> vec[3001] = {};
std::queue<int> que = {};
 
int CCW(std::pair<int, int> pair1, std::pair<int, int> pair2, std::pair<int, int> pair3)
{
	int tmp = pair1.first * pair2.second + pair2.first * pair3.second + pair3.first * pair1.second;
	tmp -= pair2.first * pair1.second + pair3.first * pair2.second + pair1.first * pair3.second;
 
	if (tmp > 0) 
		return 1; 
 
	else if (tmp < 0)
		return -1;
 
	else 
		return 0;
 
}
 
bool Check(std::pair<int, int> pair1, std::pair<int, int> pair2, std::pair<int, int> pair3, std::pair<int, int> pair4)
{
	int ans1 = CCW(pair1, pair2, pair3) * CCW(pair1, pair2, pair4);
	int ans2 = CCW(pair3, pair4, pair1) * CCW(pair3, pair4, pair2);
 
	if (!ans1 && !ans2)
	{
		if (pair1 > pair2) 
			std::swap(pair1, pair2);
 
		if (pair3 > pair4) 
			std::swap(pair3, pair4);
 
		if (pair1 <= pair4 && pair3 <= pair2)
			return true;
 
		else 
			return false;
	}
 
	else
	{
		if (ans1 <= 0 && ans2 <= 0) 
			return true;
 
		else 
			return false;
	}
}
 
int FindParent(int x)
{
	if (x == parent[x]) 
		return x;
 
	else 
		return parent[x] = FindParent(parent[x]);
}
 
bool Union(int x, int y)
{
	x = FindParent(x);
	y = FindParent(y);
 
	if (x == y)
		return false;
 
	else
	{
		parent[y] = x;
 
		graph[x].push_back(y);
		graph[y].push_back(x);
 
		return true;
	}
}
 
void BFS(int x)
{
	int num = 1;
	que.push(x);
 
	while (!que.empty())
	{
		int now = que.front();
		que.pop();
 
		visit[now] = true;
 
		for (int i = 0; i < graph[now].size(); ++i)
		{
			int next = graph[now][i];
 
			if (!visit[next])
			{
				++num;
				que.push(next);
			}
		}
	}
 
	seg = std::max(seg, num);
}
 
int main()
{
	std::cin >> N;
 
	int x1 = 0;
	int x2 = 0;
	int y1 = 0;
	int y2 = 0;
 
	for (int i = 1; i <= N; ++i)
	{
		std::cin >> x1 >> y1 >> x2 >> y2;
 
		vec[i].push_back({ x1,y1 });
		vec[i].push_back({ x2,y2 });
	}
 
	for (int i = 1; i <= N; ++i)
	{
		parent[i] = i;
	}
 
	for (int i = 1; i <= N; ++i)
	{
		for (int j = i + 1; j <= N; ++j)
		{
			bool state = Check(vec[i][0], vec[i][1], vec[j][0], vec[j][1]);
 
			if (state)
				Union(i, j);
		}
	}
 
	for (int i = 1; i <= N; ++i)
	{
		if (!visit[i])
		{
			++group;
			BFS(i); 
		}
	}
 
	std::cout << group << '\n';
	std::cout << seg << '\n';
 
	return 0;
}

 

세 개의 점으로 나눠서  CCW 체크를 해보는 게 관건입니다.

CCW 체크를 하고 시계방향인지 반시계방향인지 아니면 선분 위에 있는지 확인합니다.

두 개 다 선분 위에 있다면 선분이 평행인지, 끝점이 붙어있는지 확인합니다.

선분 두 개가 교체되는 방법은 -1 * 1(반시계, 시계) 혹은 0 * () 입니다.

교차가 된다면 둘을 엮어놓습니다.

이후에 BFS로 계산합니다.