[백준] 2162번 - 선분 그룹 (Gold 1)
업데이트:
문제 링크
문제 설명
서로 만나는 두 선분은 같은 그룹에 속하며, 그룹의 크기는 그룹에 속한 선분의 개수로 정의한다.
N개의 선분들이 주어져 있을 때 총 그룹의 개수와 가장 크기가 큰 그룹의 크기를 출력한다.
정답 코드 및 설명
선분의 교차여부 확인은 [백준] 17387번 - 선분 교차 2 (Gold 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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ2162 {
int n;
Line[] lines;
int[] parents;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Line {
Point p1, p2;
Line(int x1, int y1, int x2, int y2) {
p1 = new Point(x1, y1);
p2 = new Point(x2, y2);
}
}
void input() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
lines = new Line[n];
parents = new int[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
lines[i] = new Line(x1, y1, x2, y2);
parents[i] = -1;
}
}
boolean isCross(Line line1, Line line2) {
int point1 = crossProduct(line1.p1, line2);
int point2 = crossProduct(line1.p2, line2);
int point3 = crossProduct(line2.p1, line1);
int point4 = crossProduct(line2.p2, line1);
if (hasDiffSign(point1, point2) && hasDiffSign(point3, point4))
return true;
if (point1 == 0 && isInLine(line1.p1, line2))
return true;
if (point2 == 0 && isInLine(line1.p2, line2))
return true;
if (point3 == 0 && isInLine(line2.p1, line1))
return true;
if (point4 == 0 && isInLine(line2.p2, line1))
return true;
return false;
}
boolean isInLine(Point p, Line line) {
return crossProduct(p, line) == 0 && isIn(p.x, line.p1.x, line.p2.x) && isIn(p.y, line.p1.y, line.p2.y);
}
boolean isIn(int p, int a1, int a2) {
return (a1 <= p && p <= a2) || (a2 <= p && p <= a1);
}
boolean hasDiffSign(int x, int y) {
return (x > 0 && y < 0) || (x < 0 && y > 0);
}
int crossProduct(Point p, Line line) {
return (p.x - line.p1.x) * (p.y - line.p2.y) - (p.x - line.p2.x) * (p.y - line.p1.y);
}
int findSet(int i) {
if (parents[i] < 0) return i;
return findSet(parents[i]);
}
boolean isInSameSet(int i, int j) {
return findSet(i) == findSet(j);
}
void union(int i, int j) {
if (isInSameSet(i, j)) return;
int setI = findSet(i);
int setJ = findSet(j);
if (-parents[setI] >= -parents[setJ]) {
parents[setI] += parents[setJ];
parents[setJ] = setI;
}
if (-parents[setI] < -parents[setJ]) {
parents[setJ] += parents[setI];
parents[setI] = setJ;
}
}
void solution() throws IOException {
input();
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (isInSameSet(i, j))
continue;
if (isCross(lines[i], lines[j]))
union(i, j);
}
}
int groups = 0, maxSize = 0;
for (int i = 0; i < n; i++) {
if (parents[i] < 0) groups++;
if (-parents[i] > maxSize) maxSize = -parents[i];
}
System.out.printf("%d\n%d", groups, maxSize);
}
public static void main(String[] args) throws IOException {
new BOJ2162().solution();
}
}
댓글남기기