Algorithm/BOJ
[백준 2162] 선분 그룹 C++
Henu
2021. 6. 20. 18:46
2162번: 선분 그룹
첫째 줄에 N(1≤N≤3,000)이 주어진다. 둘째 줄부터 N+1번째 줄에는 양 끝점의 좌표가 x1, y1, x2, y2의 순서로 주어진다. 각 좌표의 절댓값은 5,000을 넘지 않으며, 입력되는 좌표 사이에는 빈칸이 하나
www.acmicpc.net
선분 교차 알고리즘, Union-Find
1. 문제 해결 아이디어
[백준 17387] 선분 교차 2 C++
17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을..
hyeo-noo.tistory.com
위 문제에서 사용했던 선분 교차 알고리즘 + Union-Find 알고리즘을 결합하면 풀 수 있는 문제이다.
N이 최대 3000개 이므로 이중 for문을 돌면서 i번 선분과 j번 선분이 교차하는지 알아본다.
만약 교차하고 i번, j번 선분이 서로 사이클을 이루지 않고 있다면
union_node함수를 실행해서 둘을 연결시켜준다.
Node배열에서 음수인 노드는 top node라고 할 수 있다.(부모 노드)
Node 값이 음수라면 그 절댓값이 부모노드와 연결된 노드의 수 이다.(부모 노드 포함)
Node를 돌면서 top node들을 찾고, top node중 절댓값이 가장 큰 값을 기록한다.
2. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
struct P{
long long x, y;
bool operator<=(P const &p1) {
if(x == p1.x){
return y <= p1.y;
}
return x <= p1.x;
}
};
struct Line{
P p1, p2;
};
Line line[3001];
int N, Node[3001];
int findTopnode(int a){
if(Node[a] < 0) return a;
return Node[a] = findTopnode(Node[a]);
}
bool is_cycle(int a, int b){
a = findTopnode(a);
b = findTopnode(b);
if(a == b) return true;
else return false;
}
void Union_node(int a, int b){
a = findTopnode(a);
b = findTopnode(b);
if(Node[a] > Node[b]){
Node[b] += Node[a];
Node[a] = b;
}
else{
Node[a] += Node[b];
Node[b] = a;
}
}
int CCW(const P &p1, const P &p2, const P &p3){
long long res = (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - \
(p2.x*p1.y + p3.x*p2.y + p1.x*p3.y);
// 행렬식을 통해서 구하기
// int determinant = (p2.x*p3.y - p2.y*p3.x) - \
// (p1.x*p3.y - p1.y*p3.x) + \
// (p1.x*p2.y - p1.y*p2.x);
if(res > 0) return 1; //반시계
else if(res < 0) return -1; //시계
else return 0;
}
bool isline_intersect(Line& l1, Line &l2){
int std1, std2;
std1 = CCW(l1.p1, l1.p2, l2.p1) * CCW(l1.p1, l1.p2, l2.p2);
std2 = CCW(l2.p1, l2.p2, l1.p1) * CCW(l2.p1, l2.p2, l1.p2);
if(std1 <= 0 && std2 <= 0){
if(std1 == 0 && std2 == 0){ //선분이 일직선인 경우
if(l1.p2 <= l1.p1) swap(l1.p1, l1.p2);
if(l2.p2 <= l2.p1) swap(l2.p1, l2.p2);
return l1.p1 <= l2.p2 && l2.p1 <= l1.p2;
}
else return true; //일직선이 아니면 교차함
}
else return false; //CCW가 같은 방향이 있으면
}
void solve(){
for(int i = 0; i < N-1; i++){
for(int j = i+1; j < N; j++){
if(isline_intersect(line[i], line[j])){
if(!is_cycle(i, j)){
Union_node(i, j);
}
}
}
}
int groupNum = 0;
int largest_groupnum = 0;
for(int i = 0; i < N; i++){
if(Node[i] < 0){
groupNum++;
largest_groupnum = max(largest_groupnum, abs(Node[i]));
}
}
cout << groupNum << "\n" << largest_groupnum;
}
void input(){
long long x1, x2, y1, y2;
P p1, p2;
cin >> N;
for(int i = 0 ; i < N; i++){
cin >> p1.x >> p1.y >> p2.x >> p2.y;
line[i].p1 = p1;
line[i].p2 = p2;
}
memset(Node, -1, sizeof(Node));
}
int main(){
input();
solve();
return 0;
}
|
cs |