문제
때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소양이 되었다.
이 작업은 크게 두 단계의 과정으로 이루어진다. 첫 번째 단계는 볼록 껍질을 이루는 점들을 찾아내는 것이고, 두 번째 단계는 이 점들을 반시계 방향으로 순서를 매기는 것이다. 첫 번째 단계는 이미 완료되었다고 할 때, 두 번째 단계를 수행하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 점의 개수 n이 주어진다. (3 <= n <= 100,000)
두 번째 줄부터 n개의 줄에 걸쳐 각 점에 대한 정보 x, y, c가 주어진다. x, y는 정수이며 절댓값이 1,000,000,000을 넘지 않고, c는 Y 또는 N인 문자이다. Y는 이 점이 볼록 껍질에 속해있음을, N이면 아님을 의미한다.
중복되는 점은 없으며, 모든 점이 한 직선 위에 있는 경우도 없다.
출력
첫 번째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.
이어서 한 줄에 하나씩 그 점들의 좌표를 x y 형태로 출력하는데, 이 점들은 반시계 방향으로 순서를 이루어야 한다. 첫 번째 좌표는 x좌표가 가장 작은 점이어야 하며, 만약 그런 좌표가 여러 개라면 그 중에서 y좌표가 가장 작은 점을 선택한다.
예제 입력
5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y예제 출력
4
-1 -1
1 -1
1 1
-1 1코드
import java.io.*;
import java.util.*;
class Point {
long x;
long y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
ArrayList<Point> points = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
String belong = st.nextToken();
if (belong.equals("Y")) { // Y인 것만 볼록 껍질
points.add(new Point(x, y));
}
}
Stack<Point> result = grahamScan(points);
bw.write(result.size() + "\n");
for (int i = 0; i < result.size(); i++) {
bw.write(result.get(i).x + " " + result.get(i).y + "\n");
}
br.close();
bw.flush();
bw.close();
}
static Point root = new Point(Long.MAX_VALUE, Long.MAX_VALUE);
static Stack<Point> grahamScan(ArrayList<Point> input) throws IOException {
// 기준점 찾기
for (int i = 0; i < input.size(); i++) {
if (input.get(i).x < root.x) {
root = input.get(i);
} else if (input.get(i).x == root.x) {
if (input.get(i).y < root.y) {
root = input.get(i);
}
}
}
// 모든 점들을 반시계 방향으로 정렬하기
input.sort(new Comparator<Point>() {
@Override
public int compare(Point p1, Point p2) { // return 1이면 자리를 바꾼다
int result = ccw(root, p1, p2);
if (result > 0) {
return -1;
} else if (result < 0) {
return 1;
} else {
long distance1 = dist(root, p1);
long distance2 = dist(root, p2);
if (distance1 > distance2) { // 거리가 더 가까운 순으로 정렬
return 1;
}
}
return -1;
}
});
Stack<Point> stack = new Stack<>();
stack.add(root);
for (int i = 1; i < input.size(); i++) {
while (stack.size() > 1 && (ccw(stack.get(stack.size() - 2), stack.get(stack.size() - 1), input.get(i)) < 0)) { // first, second, next
stack.pop(); // second 빼기
}
stack.add(input.get(i)); // next 넣기
}
ArrayList<Point> extra_points = new ArrayList<>();
// input에 있는 값인데 stack에 없는 경우 추가해줘야함
for (int i = 1; i < input.size(); i++) {
if (!stack.contains(input.get(i))) {
extra_points.add(input.get(i));
}
}
extra_points.sort(new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
long distance1 = dist(root, o1);
long distance2 = dist(root, o2);
if (distance1 < distance2) {
return 1;
}
return -1;
}
});
stack.addAll(extra_points);
return stack;
}
static int ccw(Point p1, Point p2, Point p3) {
long result = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);
if (result > 0) { // 반시계 방향
return 1;
} else if (result < 0) { // 시계 방향
return -1;
} else {
return 0;
}
}
static long dist(Point p1, Point p2) {
return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
}
}정리
- 기존에 y가 가장 작은 값으로 기준점을 잡았었는데, 이 문제에서는 x가 가장 작은 값으로 잡아야 했다.
- 볼록 껍질에 속하는 모든 점을 출력해야 하기 때문에
CCW = 0인 값은 pop 하지 않았다. - 볼록 껍질(➡️⬆️⬅️⬇️)의 마지막 선분(⬇️) 위에 속하는 점들은 처음 sorting 할 때 distance로 비교하여 가까운 점 순으로 정렬된다. 그로 인해 중간에 first, second, next 값으로 CCW를 판별하는 과정에서 CW로 판별되어 pop 되므로 마지막에 다시 추가해 주어야 한다.
- Y로 입력받았는데 stack에 쌓이지 않은 값들을 모아서, 마지막에 distance가 큰 값부터 stack에 쌓아줬다.
코드 - Monotone chain
import java.io.*;
import java.util.*;
class Point {
long x;
long y;
Point(long x, long y) {
this.x = x;
this.y = y;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
ArrayList<Point> points = new ArrayList<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
String belong = st.nextToken();
if (belong.equals("Y")) { // Y인 것만 볼록 껍질
points.add(new Point(x, y));
}
}
Stack<Point> result = grahamScan(points);
bw.write(result.size() + "\n");
for (int i = 0; i < result.size(); i++) {
bw.write(result.get(i).x + " " + result.get(i).y + "\n");
}
br.close();
bw.flush();
bw.close();
}
static Stack<Point> grahamScan(ArrayList<Point> input) throws IOException {
// 모든 점들을 x 오름차순으로 정렬하기
input.sort(new Comparator<Point>() {
@Override
public int compare(Point p1, Point p2) { // return 1이면 자리를 바꾼다
if (p1.x > p2.x) {
return 1;
} else if (p1.x == p2.x) {
if (p1.y > p2.y) {
return 1;
}
}
return -1;
}
});
Stack<Point> lower = new Stack<>(); // 아래 껍질
Stack<Point> upper = new Stack<>(); // 위 껍질
// 아래 껍질 계산
for (int i = 0; i < input.size(); i++) {
while (lower.size() > 1 && (ccw(lower.get(lower.size() - 2), lower.get(lower.size() - 1), input.get(i)) < 0)) { // first, second, next
lower.pop();
}
lower.add(input.get(i));
}
// 위 껍질 계산
for (int i = input.size() - 1; i >= 0; i--) {
while (upper.size() > 1 && (ccw(upper.get(upper.size() - 2), upper.get(upper.size() - 1), input.get(i)) < 0)) { // first, second, next
upper.pop();
}
upper.add(input.get(i));
}
lower.pop(); // 중복 제거
upper.pop();
lower.addAll(upper);
return lower;
}
static int ccw(Point p1, Point p2, Point p3) {
long result = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y) - (p2.x * p1.y + p3.x * p2.y + p1.x * p3.y);
if (result > 0) { // 반시계 방향
return 1;
} else if (result < 0) { // 시계 방향
return -1;
} else {
return 0;
}
}
}정리 - Monotone chain
Monotone chain으로도 풀 수 있다는 것을 알게 되어 한번 구현해봤는데 코드가 훨씬 간단해졌다.- 각도에 따른 정렬이 아닌, x 값에 따라 오름차순으로 정렬한 뒤 for 문을 2번 돌리면 되는 것이었다.
참고링크
https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
기억하기 위해 기록하는 개발로그👣