선분 그룹이라는 문제는 기하 알고리즘 문제풀이의 기초이자 꽃이라고 할 수 있는 CCW를 이용하는 동시에 유니온 파인드를 섞어 놓은 문제였다. 문제를 보면서 대충 어떤 식으로 풀면되겠다는 것이 머리 속에 그려져서 로직도 금방 세우고 코딩도 금방했는데 의외로 계속 오답이 나서 짜증나는 문제였다.
문제를 살펴보면 여러 선분이 주어졌을 때, 만일 선분끼리 교차되거나 겹치게 되면 그 선분들은 하나의 그룹이 된다. 이 때 선분들을 몇 개의 그룹으로 묶을 수 있고 그룹 중에 가장 많은 선분을 포함하고 있는 그룹에 속한 선분이 몇 개인지 출력하면 된다. 문제를 보고 생각난 것은 CCW였다. 기하 문제를 풀어본 사람은 알겠지만, CCW를 이용하면 두 선분의 교차 여부를 쉽게 파악할 수 있다. 만일 CCW가 익숙하지 않은 사람이라면 블로그의 CCW를 참고하도록 하자.
물론 CCW 자체가 교차 여부를 가르쳐 주지는 않지만 CCW를 이용하여 교차 여부를 판단할 수 있다. 우선 하나의 선분을 기준으로 하여 다른 선분의 두 점의 위치를 파악한다. 만일 선분과 한 점의 CCW 값이 음수로 나왔는데 다른 한 점의 CCW 값이 양수로 나왔다면 이는 적어도 선분을 기준으로 두 점이 각각 왼편과 오른편에 존재한다는 것을 의미한다. 이제 그 상태에서 다른 한 선분을 기준으로 기존의 기준이 되었던 선분의 양 끝점의 CCW를 구했을 때 아까와 마찬가지로 음수, 양수로 교차하여 나오게 되면 이 두 선분은 서로 교차한다는 것을 알 수 있다.
교차는 쉽게 구했는데 문제는 T자 모양으로 한점이 다른 선분 위에 존재하거나 ㄱ이나 ㄴ모양으로 한 점에서 두 선분이 만나는 경우였다. 이 경우 CCW 중 하나는 0이 나오게 되기 때문에 아까의 음수, 양수 조건에다 0까지 포함시키도록 로직을 구성했다. 그랬더니 다시 문제가 하나 발생했는데 이번에는 같은 기울기를 가진 두 선분이 서로 만나지 않는 경우가 있는데 위의 로직으로는 이를 구별할 수 있는 방법이 없었던 것이다. 문제를 해결할 이렇다할 방법이 없어서 고민했는데, 이러한 경우는 두 선분을 각각 기준으로 하였을 때 양 쪽 CCW 모두 0이 나오는 경우이기 때문에 이 조건으로 분기시킨 뒤 두 선분이 만날 수 없는 조건으로 겹치는지 겹치지 않는지 판단하여 겹치지 않는 경우라면 같은 그룹으로 편입시키지 않는 것으로 결론을 내렸다. 두 선분이 겹치지 않는 조건은 한 선분의 최소 x좌표값보다 다른 선분의 최대 x좌표의 값이 더 작다면 두 선분이 마주치지 않는다는 것을 이용하였으며, 그 반대의 경우와 y좌표의 경우도 모두 포함시켜 빠지는 케이스가 없도록 함수로 구현하였다.
CCW 및 유니온 파인드의 구현은 Algorithm for Beginners와 Algorithm study의 설명을 참고하도록 하자.
백준 온라인 저지의 선분 그룹 문제 풀이는 아래와 같다.
package acmicpc_2162;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main {
private static int[] par;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int N = Integer.parseInt(br.readLine().trim());
Line[] l = new Line[N + 1];
par = new int[N + 1];
for (int i = 1; i <= N; i++) {
par[i] = i;
}
long x1, y1, x2, y2;
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine().trim());
x1 = (long) Integer.parseInt(st.nextToken());
y1 = (long) Integer.parseInt(st.nextToken());
x2 = (long) Integer.parseInt(st.nextToken());
y2 = (long) Integer.parseInt(st.nextToken());
l[i] = new Line(x1, y1, x2, y2);
}
int iPar, jPar;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (i == j)
continue;
iPar = find(i);
jPar = find(j);
if (iPar != jPar) {
if (isCrossed(l[i], l[j])) {
union(i, j);
}
}
}
}
int[] count = new int[N + 1];
for (int i = 1; i <= N; i++) {
count[par[i]]++;
}
int max = 0;
int size = 0;
for (int i = 1; i <= N; i++) {
if (max < count[i])
max = count[i];
if (count[i] != 0) {
size++;
}
}
System.out.println(size);
System.out.println(max);
}
private static boolean isCrossed(Line l1, Line l2) {
long chk1 = CCW(l1.x1, l1.y1, l1.x2, l1.y2, l2.x1, l2.y1) * CCW(l1.x1, l1.y1, l1.x2, l1.y2, l2.x2, l2.y2);
long chk2 = CCW(l2.x1, l2.y1, l2.x2, l2.y2, l1.x1, l1.y1) * CCW(l2.x1, l2.y1, l2.x2, l2.y2, l1.x2, l1.y2);
if (chk1 == 0 && chk2 == 0) {
return isOverlapped(l1, l2);
}
return chk1 <= 0 && chk2 <= 0;
}
private static boolean isOverlapped(Line l1, Line l2) {
if (Math.max(l1.x1, l1.x2) < Math.min(l2.x1, l2.x2))
return false;
if (Math.min(l1.x1, l1.x2) > Math.max(l2.x1, l2.x2))
return false;
if (Math.max(l1.y1, l1.y2) < Math.min(l2.y1, l2.y2))
return false;
if (Math.min(l1.y1, l1.y2) > Math.max(l2.y1, l2.y2))
return false;
return true;
}
private static int CCW(long x1, long y1, long x2, long y2, long x3, long y3) {
long tmp = x1 * y2 + x2 * y3 + x3 * y1;
tmp -= (y1 * x2 + y2 * x3 + y3 * x1);
if (tmp < 0)
return -1;
if (tmp > 0)
return 1;
return 0;
}
private static void union(int i, int j) {
int p = find(i);
int q = find(j);
if (p == q)
return;
par[q] = p;
}
private static int find(int i) {
if (par[i] == i)
return i;
return par[i] = find(par[i]);
}
}
class Line {
long x1;
long y1;
long x2;
long y2;
public Line(long x1, long y1, long x2, long y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
}