백준 2162 c++ - [PlusUltraCode]

[필자 사고]

 

백준 17387번으로 선분의 교차여부를 코드로 작성하였다. 
이 문제는 그에 더해서 Union 알고리즘을 사용하여 문제를 해결할 수 있는지 묻는 문제였다.

먼저 선분의 교차여부 알고리즘을 만들고 Union 알고리즘을 아용하여 그룹의 최대 갯수를 구했다.

 

#include<iostream>
#include <vector>
#include<cmath>
#include <algorithm>

using namespace std;

typedef struct Point {
	long x1, y1, x2, y2;
}Point;

vector<int> parent;
vector<bool> visited;
vector<long> groupCount;
int find(int a) {
	if (a == parent[a])return a;
	else return parent[a] = find(parent[a]);
}

void Union(int a, int b) {
	a = find(a);
	b = find(b);
	if (a != b) {
		parent[b] = a;
	}
}
bool isSame(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return true;
	else return false;
}

int N;
vector<Point> Line;

int CCW(long x1, long y1, long x2, long y2, long x3, long y3) {
	// x1 x2 x3 x1
	// y1 y2 y3 y1
	long ccw = (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3);
	if (ccw == 0)return 0;
	else if (ccw > 0)return 1;
	else return -1;

}
bool isOverlab(Point L1 ,Point L2) {
	long x1 = L1.x1;
	long y1 = L1.y1;
	long x2 = L1.x2;
	long y2 = L1.y2;
	long x3 = L2.x1;
	long y3 = L2.y1;
	long x4 = L2.x2;
	long y4 = L2.y2;

	if (min(x1, x2) <= max(x3, x4) && min(x3, x4) <= max(x1, x2) &&
		min(y1, y2) <= max(y3, y4) && min(y3, y4) <= max(y1, y2)) {
		return true;
	}
	else return false;

}
bool isCross(Point L1, Point L2) {
	long x1 = L1.x1;
	long y1 = L1.y1;
	long x2 = L1.x2;
	long y2 = L1.y2;
	long x3 = L2.x1;
	long y3 = L2.y1;
	long x4 = L2.x2;
	long y4 = L2.y2;
	long abc = CCW(x1, y1, x2, y2, x3, y3);
	long abd = CCW(x1, y1, x2, y2, x4, y4);
	long cda = CCW(x3, y3, x4, y4, x1, y1);
	long cdb = CCW(x3, y3, x4, y4, x2, y2);
	if (abc * abd == 0 && cda * cdb==0) {
		if (isOverlab(L1, L2)) {
			return true;
		}
	}
	else if (abc * abd <= 0 && cda * cdb <= 0)return true;
	return false;

}


void Input() {
	cin >> N;
	Line.resize(N + 1);
	parent.resize(N );
	visited.resize(N,false);
	groupCount.resize(N);
	for (int i = 0; i < N; i++) {
		parent[i] = i;
	}
	for (int i = 0; i < N; i++) {
		long a, b, c, d;
		cin >> a >> b >> c >> d;
		Line[i].x1 = a;
		Line[i].y1 = b;
		Line[i].x2 = c;
		Line[i].y2 = d;
	}

}

void Solve() {
	for (int i = 0; i < N-1; i++) {
		for (int k = i+1; k < N; k++) {
			if (isCross(Line[i], Line[k])) {
				Union(i, k);
			}
		}
	}
	for (int i = 0; i < N; i++) {
		int n = find(i);
	}
	
	for (int i = 0; i < N; i++) {
		groupCount[parent[i]]++;
	}
	long maxNumber = *max_element(groupCount.begin(), groupCount.end());
	long Group = 0;
	for (int i = 0; i < N; i++) {
		if (groupCount[i] != 0) {
			Group++;
		}
	}
	cout << Group << '\n' << maxNumber;
	
}


int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	Input();
	Solve();



}