2162번: 선분 그룹 - CCW, 유니온 파인드

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

2162번: 선분 그룹

 

두 선분이 교차하는 지 알아낸 후 이를 유니온 파인드를 이용해 집합으로 표현하는 문제이다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int N;
int line[3001][5];
int par[3001];
int height[3001];
int group[3001];

bool isCross(int, int);
int getPar(int);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i{ 1 }; i <= N; i++)
	{
		for (int j{ 1 }; j <= 4; j++)
		{
			cin >> line[i][j];
		}
	}

	for (int i{ 1 }; i <= N; i++)
	{
		for (int j{ i + 1 }; j <= N; j++)
		{
			if (isCross(i, j)) //두 선분이 교차한다면
			{
				int a{ getPar(i) };
				int b{ getPar(j) };

				if (a == b) continue;

				if (height[a] > height[b]) par[b] = a;
				else
				{
					par[a] = b;
					if (height[a] == height[b]) height[b]++;
				}
			} //유니온 파인드를 이용해 집합으로 표현한다.
		}
	}

	for (int i{ 1 }; i <= N; i++)
	{
		int k{ getPar(i) };
		if(i != k) par[i] = k;
	} //각 선분의 대푯값을 확실히 한다.

	int groupCnt{ 0 }; //대푯값의 수
	int mx{ 0 }; //집합의 최대 크기
	for (int i{ 1 }; i <= N; i++)
	{
		if (par[i] == 0) //대푯값일 때
		{
			groupCnt++;
			group[i]++;
			mx = max(mx, group[i]);
		}
		else
		{
			group[par[i]]++;
			mx = max(mx, group[par[i]]);
		}
	}
	cout << groupCnt << "\n" << mx << "\n";
}

bool isCross(int a, int b)
{
	ll p2p1x = line[a][3] - line[a][1]; ll p2p1y = line[a][4] - line[a][2];
	ll p2p3x = line[a][3] - line[b][1]; ll p2p3y = line[a][4] - line[b][2];
	ll p2p4x = line[a][3] - line[b][3]; ll p2p4y = line[a][4] - line[b][4];

	ll p4p3x = line[b][3] - line[b][1]; ll p4p3y = line[b][4] - line[b][2];
	ll p4p1x = line[b][3] - line[a][1]; ll p4p1y = line[b][4] - line[a][2];
	ll p4p2x = line[b][3] - line[a][3]; ll p4p2y = line[b][4] - line[a][4];

	ll ccw1 = p2p1x * p2p3y - p2p1y * p2p3x;
	ll ccw2 = p2p1x * p2p4y - p2p1y * p2p4x;
	ll ccw3 = p4p3x * p4p1y - p4p3y * p4p1x;
	ll ccw4 = p4p3x * p4p2y - p4p3y * p4p2x;

	bool cross{ true };
	if ((ccw1 < 0 && ccw2 < 0) || (ccw1 > 0 && ccw2 > 0)) cross = false;
	if ((ccw3 < 0 && ccw4 < 0) || (ccw3 > 0 && ccw4 > 0)) cross = false;
	if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0)
	{
		if (max(line[a][1], line[a][3]) < min(line[b][1], line[b][3])) cross = false;
		if (min(line[a][1], line[a][3]) > max(line[b][1], line[b][3])) cross = false;
		if (max(line[a][2], line[a][4]) < min(line[b][2], line[b][4])) cross = false;
		if (min(line[a][2], line[a][4]) > max(line[b][2], line[b][4])) cross = false;
	}
	return cross;
} //CCW를 이용해 두 선분이 교차하는지 알아낸다.

int getPar(int k)
{
	if (par[k] == 0) return k;
	else return getPar(par[k]);
}