BOJ 2162. 선분 그룹
랭크 : 플레티넘4
문제 풀이
2개의 선분이 주어졌을 때, 한 선분에서 다른 선분의 요소에 대해서 외적을 취하여 이들의 부호가 -라면 각각 다른 방향에 존재하고, +라면 같은 방향에 존재하기 때문에, -임을 확인하면 됩니다. 이를 양쪽 선분에 대해서 모두 수행하고, 만약 같은 선상에 있어 외적이 0이라면, 두 선분 사이에 점이 존재하는지 안하는 지를 확인하여, 이후에 union-find를 통해 그룹을 나누어 정리하면 됩니다.
제출 했을 때 틀린 부분은, 먼저 자료형 long long으로 해주는 부분과, 한 선분 위에 점 4개가 있을 때 x좌표로만 비교를 해주었는데, x좌표가 동일하고 y좌표만 다른 경우가 존재해 이런 경우 처리를 따로 해주었습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
struct Point {
long long x;
long long y;
Point() : x(0), y(0) {};
Point(long long _x, long long _y) : x(_x), y(_y) {};
Point operator-(const Point& ref) {
return Point(ref.x - x, ref.y - y);
}
long long operator*(const Point& ref) {
return ref.x * y - x * ref.y;
}
};
Point lines[3001][2];
long long parents[3001];
long long num[3001];
long long visited[3001];
long long N;
long long CrossProduct(Point x, Point y, Point z) {
return (x - y) * (x - z);
};
bool CCW(Point x1, Point x2, Point y1, Point y2) {
long long result1 = CrossProduct(x1, x2, y1) * CrossProduct(x1, x2, y2);
long long result2 = CrossProduct(y1, y2, x1) * CrossProduct(y1, y2, x2);
if (result1 == 0 && result2 == 0) {
if (x1.x != x2.x) {
long long minx = min(x1.x, x2.x);
long long miny = min(y1.x, y2.x);
if (minx <= miny) {
if (minx <= miny && miny <= max(x1.x, x2.x)) return true;
} else {
if (miny <= minx && minx <= max(y1.x, y2.x)) return true;
}
} else {
long long minx = min(x1.y, x2.y);
long long miny = min(y1.y, y2.y);
if (minx <= miny) {
if (minx <= miny && miny <= max(x1.y, x2.y)) return true;
} else {
if (miny <= minx && minx <= max(y1.y, y2.y)) return true;
}
}
return false;
} else if (result1 <= 0 && result2 <= 0) {
return true;
}
return false;
}
long long FindParents(long long a) {
if (parents[a] == a) return a;
return parents[a] = FindParents(parents[a]);
};
void isUnion(long long a, long long b) {
a = FindParents(a);
b = FindParents(b);
if (a == b) return;
num[b] += num[a];
num[a] = num[b];
// 더 작은 값이 부모 노드가 될 수 있도록
if (a < b) {
parents[b] = a;
}
else {
parents[a] = b;
}
}
bool UnionFind(long long a, long long b) {
a = FindParents(a);
b = FindParents(b);
return (a == b);
}
int main() {
fastio;
long long tmp1, tmp2, tmp3, tmp4;
cin >> N;
for (long long i=0; i < N; i++) {
cin >> tmp1 >> tmp2 >> tmp3 >> tmp4;
lines[i][0].x = tmp1;
lines[i][0].y = tmp2;
lines[i][1].x = tmp3;
lines[i][1].y = tmp4;
num[i] = 1;
parents[i] = i;
}
for (long long i= 0; i < N - 1; i++) {
for (long long j= i + 1; j < N; j++) {
if (CCW(lines[i][0], lines[i][1], lines[j][0], lines[j][1])) {
isUnion(i, j);
}
}
}
long long group_num = 0;
for (long long i=0; i < N; i++) {
long long tmp = FindParents(i);
if (visited[tmp] == 0) {
group_num++; visited[tmp]++;
}
}
cout << group_num << endl;
cout << *max_element(num, num + N) << endl;
}
알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| union_find | O(N^2) | O(N) |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 2887. 행성 터널 (0) | 2022.07.07 |
|---|---|
| BOJ 1007. 벡터 매칭 (0) | 2022.07.07 |
| BOJ 2623. 음악프로그램 (0) | 2022.07.06 |
| BOJ 17387. 선분 교차2 (0) | 2022.07.06 |
| BOJ 2342. Dance Dance Revolution (0) | 2022.07.06 |