[수학 4 단계] 백준 2162번 선분 그룹

문제

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

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

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

입력

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

출력

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

 

두 라인의 접촉은 일반 교차 , 평행 교차이다. 접하는 것 또한 교차에 포함되어 있음.

두 라인은 결국 점 4개로 구성되어 있고 이걸로 CCW를 통해 교차 여부를 판단하고

둘이 교차한다면 union find로 부모 관계를 맺는다.

그리고 1번 부터 n번까지 탐색하면서 자신 자체가 부모면 그것이 곧 그룹1개를 의미하고 

자신이 부모가 아니면 타고올라가면서 최종 부모에서 카운트를 1씩 늘려준다.

#include <iostream>
#include<vector>
#include <algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
int N;
pair<pair<int, int>,pair<int,int> > line[5001];
int parent[5001];
int num[5001];


int findParent(int node)
{
	if (node == parent[node])
		return parent[node];
	return parent[node] = findParent(parent[node]);
}

int CCW(pair<int, int> A, pair<int, int> B, pair<int, int> C)
{
	long long op = A.first * B.second + B.first * C.second + C.first * A.second;
	op -= A.second * B.first + B.second * C.first + C.second * A.first;
	if (op > 0)
		return 1;
	else if (op == 0)
		return 0;
	else
		return -1;
}


bool intersect(int line1, int line2)
{
	pair<int, int> A = line[line1].first;
	pair<int, int> B = line[line1].second;
	pair<int, int> C = line[line2].first;
	pair<int, int> D = line[line2].second;

	int abc = CCW(A, B, C);
	int abd = CCW(A, B, D);
	int cda = CCW(C, D, A);
	int cdb = CCW(C, D, B);
	if (abc * abd == 0 && cda * cdb == 0)
	{
		if (A > B)swap(A, B);
		if (C > D)swap(C, D);
		if (A <= D && C <= B)return true;
		return false;
	}

	if (abc * abd <= 0 && cda * cdb <= 0)
	{
		return true;
	}
	else
	{
		return false;
	}

}

int main() {

	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		cin >> line[i].first.first >> line[i].first.second >> line[i].second.first >> line[i].second.second;
		parent[i] = i;
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = i + 1; j <= N; j++)
		{
			if (intersect(i, j))
			{
				int node1 = findParent(i);
				int node2 = findParent(j);
				parent[node2] = node1;
			}
		}
	}

	int maxa = 0;
	int group = 0;
	for (int i = 1; i <= N; i++)
	{
		if (parent[i] == i)
		{
			group++;
			num[i]++;
			if (num[i] > maxa)
			{
				maxa = num[i];
			}
		}
		else
		{
			int node = findParent(i);
			num[node]++;
			if (num[node] > maxa)
			{
				maxa = num[node];
			}
		}
	}
	cout << group << endl;
	cout << maxa << endl;
}