문제
다각형의 임의의 두 꼭짓점을 연결하는 선분이 항상 다각형 내부에 존재하는 다각형을 볼록 다각형이라고 한다. 아래 그림에서 (a)는 볼록 다각형이며, (b)는 볼록 다각형이 아니다.
조금만 생각해 보면 다각형의 모든 내각이 180도 이하일 때 볼록 다각형이 된다는 것을 알 수 있다. 편의상 이 문제에서는 180도 미만인 경우만을 볼록 다각형으로 한정하도록 한다.
2차원 평면에 N개의 점이 주어졌을 때, 이들 중 몇 개의 점을 골라 볼록 다각형을 만드는데, 나머지 모든 점을 내부에 포함하도록 할 수 있다. 이를 볼록 껍질 (CONVEX HULL) 이라 한다. 아래 그림은 N=10인 경우의 한 예이다.
점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범위는 절댓값 40,000을 넘지 않는다. 입력으로 주어지는 다각형의 모든 점이 일직선을 이루는 경우는 없다.
출력
첫째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.
볼록 껍질의 변에 점이 여러 개 있는 경우에는 가장 양 끝 점만 개수에 포함한다.
예제 입력
8
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2예제 출력
5코드
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());
points.add(new Point(x, y));
}
bw.write(grahamScan(points) + "\n");
br.close();
bw.flush();
bw.close();
}
static Point root = new Point(Long.MAX_VALUE, Long.MAX_VALUE);
static int grahamScan(ArrayList<Point> input) {
// 기준점 찾기
for (int i = 0; i < input.size(); i++) {
if (input.get(i).y < root.y) {
root = input.get(i);
} else if (input.get(i).y == root.y) {
if (input.get(i).x < root.x) {
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 넣기
}
return stack.size();
}
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);
}
}정리
2학년 2학기 알고리즘 수업에서 Graham Scan과 Jarvis March 알고리즘을 배웠다. (그러나 잘 기억이 나지 않아 검색해보았다..)
- Jarvis March의 시간 복잡도는 점의 개수 n과 볼록 껍질을 이루는 점의 개수 h에 대해
O(nh)이다. - 반면, Graham Scan의 시간 복잡도는
O(nlogn)이다. 점들을 정렬하는 시간이 볼록 껍질을 계산하는 시간을 지배한다.
알고리즘
1. y가 가장 작은 값으로 기준점을 잡는다. (y가 같다면 둘 중 x가 작은 값)
2. 기준점을 기준으로 다른 점들을 반시계 방향으로 각에 따라 정렬한다.
3. Stack에 0~1번째 값까지 넣은 후,
4. first, second, next 세 값으로 CCW 인지 판별한다.
5. CCW 면 next를 Stack에 넣고, CCW가 아니면 second를 빼고 CCW 인지 다시 확인한다.
6. 주어진 점의 개수만큼 4~5번을 반복한다.스택에 쌓고 뽑으며 CCW 인지 판별하는 과정은 어렵지 않았지만, sorting 하는 과정이 어려웠다.
두 점을 비교하여 만약 CW라면 두 점의 위치를 바꾸어 주어야 했다.
또, 두 점을 비교했을 때 CCW의 리턴 값이 0이라면 같은 직선에 위치하는 것이므로 distance를 비교하여 더 가까운 순으로 정렬해 주어야 했다.
참고 링크
