[수학: 선분 교차] 선분 교차(ccw 활용) + 유니온-파인드: 예제 문제: 선분 그룹_백준

예제 문제: 선분 그룹_백준

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

typedef long long ll;

int N;

struct Point {
	ll x;
	ll y;

	bool operator<(Point p) {
		if (x != p.x)
			return x < p.x;
		else
			return y < p.y;
	}

	bool operator<=(Point p) {
		if (x == p.x && y == p.y)
			return true;
		else
			return (*this) < p;
	}
};
struct Line {
	Point p1;
	Point p2;

	Line(ll x1, ll y1, ll x2, ll y2) {
		p1.x = x1;
		p1.y = y1;
		p2.x = x2;
		p2.y = y2;
	}
};

class UF_SET {
private:
	vector<int>* parentTable;
	int nodeNum;

public:
	UF_SET(int n) {
		nodeNum = n;
		parentTable = new vector<int>(nodeNum);

		for (int i = 0; i < nodeNum; i++) {
			(*parentTable)[i] = i;
		}
	}

	void Union(int node1, int node2) {
		int node1Parent = FindParent(node1);
		int node2Parent = FindParent(node2);

		if (node1Parent < node2Parent)
			(*parentTable)[node2Parent] = node1Parent;
		else
			(*parentTable)[node1Parent] = node2Parent;
	}

	int FindParent(int node) {
		if ((*parentTable)[node] == node)
			return node;
		else
			return (*parentTable)[node] = FindParent((*parentTable)[node]);
	}
	
	pair<int, int> getParentGroupNumAndMaxNum() {
		
		unordered_map<int, int> groups;
		
		for (int i = 0; i < nodeNum; i++) {
			int node = i;
			int parent = FindParent(node);

			if (groups.find(parent) == groups.end()) {
				groups.insert({ parent, 1 });
			}
			else
				groups[parent]++;
		}

		// max group num
		int maxNum = 0;
		for (auto iter = groups.begin(); iter != groups.end(); iter++) {
			maxNum = max(maxNum, (*iter).second);
		}

		return { groups.size(), maxNum };
	}
};

// 선분 교차 여부 함수
int ccw(Point p1, Point p2, Point p3) {
	ll op1 = (p2.x - p1.x) * (p3.y - p1.y);
	ll op2 = (p2.y - p1.y) * (p3.x - p1.x);
	ll op = op1 - op2;
	if (op > 0)
		return 1;
	else if (op == 0)
		return 0;
	else
		return -1;
}

bool checkLineCross(Line line1, Line line2) {
	int ccwCheck1 = ccw(line1.p1, line1.p2, line2.p1) * ccw(line1.p1, line1.p2, line2.p2);
	int ccwCheck2 = ccw(line2.p1, line2.p2, line1.p1) * ccw(line2.p1, line2.p2, line1.p2);


	if (ccwCheck1 <= 0 && ccwCheck2 <= 0) {
		//선분이 일직선인 경우
		if (ccwCheck1 == 0 && ccwCheck2 == 0) {     
			if (line1.p2 <= line1.p1) {
				Point temp = line1.p1;
				line1.p1 = line1.p2;
				line1.p2 = temp;
			}
			if (line2.p2 <= line2.p1) {
				Point temp = line2.p1;
				line2.p1 = line2.p2;
				line2.p2 = temp;
			}

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

pair<int, int> solution(const vector<Line>& points) {
	// 초기화
	UF_SET ufSet(N);


	for (int i = 0; i < N; i++) {
		Line nowLine = points[i];
		for (int j = 0; j < i; j++) {
			Line beforeLine = points[j];

			// if(선분이 교차한다면)
			//		유니온!
			if (checkLineCross(nowLine, beforeLine)) {
				ufSet.Union(i, j);
			}
		}
	}

	return ufSet.getParentGroupNumAndMaxNum();
}

int main() {
	cin >> N;
	vector<Line> points;
	for (int i = 0; i < N; i++) {
		ll x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		Line line(x1, y1, x2, y2);
		points.push_back(line);
	}

	pair<int, int> answer = solution(points);

	cout << answer.first << endl;
	cout << answer.second << endl;
	
	return 0;
}