📌 문제 개요

2차원 평면 위에 N개의 점이 주어진다.
이 점들 중 일부를 선택해 볼록 다각형(Convex Polygon) 을 만들고,
그 다각형을 이루는 점의 개수를 구하는 문제이다.

문제의 핵심 조건은 다음과 같다.

• 다각형의 모든 내각은 180도 이하
  
• 선택한 점들로 만든 다각형은 모든 점을 포함해야 한다
  

즉, 우리는 Convex Hull (볼록 껍질) 을 구해야 한다.

---

✨ 접근 방법 — Graham Scan

이 문제는 대표적인 볼록 껍질 알고리즘인 Graham Scan 으로 해결할 수 있다.

Graham Scan의 전체 흐름은 다음과 같다.

1. 기준점(root)을 정한다
2. 기준점을 기준으로 반시계 방향 정렬을 한다
3. 스택을 이용해 항상 “좌회전(반시계)”만 유지한다
4. 시계 방향이 나오면 직전 점을 제거한다

이 과정을 통해 자연스럽게 가장 바깥 점들만 남게 된다.

---

1️⃣ 기준점(root) 선택

기준점은 다음 기준으로 선택한다.

• y 값이 가장 작은 점
  
• y 값이 같다면 x 값이 가장 작은 점
  

이 점은 반드시 볼록 껍질에 포함된다.
가장 아래에 위치한 점이므로 내부에 포함될 수 없기 때문이다.

코드는 다음과 같이 구현하였다.

for (int i = 0; i < points.size(); i++) {
    if (points.get(i).y < root.y) {
        root = points.get(i);
    } else if (points.get(i).y == root.y) {
        if (points.get(i).x < root.x) {
            root = points.get(i);
        }   
    }
}

---

2️⃣ 반시계 방향 정렬

이제 기준점을 중심으로 나머지 점들을 반시계 방향(CCW) 으로 정렬한다.

여기서 사용하는 것이 ccw() 연산이다.

ccw(p1, p2, p3)의 의미는 다음과 같다.

• 양수 → 반시계 방향
  
• 음수 → 시계 방향
  
• 0 → 일직선(평행)
  

정렬 기준은 다음과 같다.

• 반시계 방향에 있는 점이 앞으로 오도록 한다
  
• 만약 ccw 값이 0이라면 (평행)
  → 기준점에서 더 가까운 점이 먼저 오도록 한다
  

코드는 다음과 같다.

Collections.sort(points, (p1, p2) -> {
    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;
        } else {
            return -1;
        }
    }
});

여기서 평행한 경우 가까운 점을 먼저 두는 이유는
이후 스택 처리 과정에서 자동으로 먼 점만 남기기 위함이다.

---

3️⃣ 스택을 이용한 볼록성 유지

이제 정렬된 점들을 순서대로 보면서 볼록 다각형을 구성한다.

핵심 아이디어는 다음과 같다.

마지막 두 점과 새 점이
반시계 방향이 아닐 경우 제거한다.

구현 코드는 다음과 같다.

Stack<Point> stack = new Stack<>();
stack.add(root);

for (int i = 1; i < points.size(); i++) {
    while (stack.size() > 1 && ccw(stack.get(stack.size() - 2), stack.get(stack.size() - 1), points.get(i)) <= 0) {
        stack.pop();
    }
    stack.add(points.get(i));
}

🔍 이 코드의 의미

• stack에는 현재까지 선택된 볼록 껍질의 꼭짓점들이 들어간다.
  
• 마지막 두 점과 새 점이
  • 시계 방향이거나
    
  • 일직선이라면
    
• 이는 내부로 꺾이는 형태이므로 제거한다.
  

이 과정을 반복하면 항상 “좌회전”만 유지되게 된다.
즉, 모든 내각이 180도 이하가 된다.

---

4️⃣ 평행한 점 처리

정렬 단계에서 같은 방향(평행)일 경우 가까운 점을 먼저 배치했다.

이후 스택 단계에서

• 더 먼 점이 들어올 때
  
• ccw == 0이 되어
  
• 가까운 점이 pop 된다
  

결과적으로 같은 직선 위에서는 가장 먼 점만 남게 된다.

---

5️⃣ 왜 모든 점을 포함하는가?

기준점을 가장 아래 점으로 선택했고,
항상 반시계 방향만 유지하도록 구성했기 때문에

• 내부 점은 반드시 어느 순간 시계 방향을 만들게 되고
  
• 그 순간 pop 되어 제거된다
  

결국 남는 점들은 가장 바깥을 감싸는 점들뿐이다.

즉, 최종 stack에 남아 있는 점들이 바로 Convex Hull이다.

---

🔢 전체 코드

(코드 부분은 그대로 유지)

// 전체 코드 생략 없이 그대로 삽입
import java.util.*;
import java.io.*;
import java.util.function.Function;

public class Main {
    static List<Point> points = new ArrayList<>();
    static Point root = new Point(Long.MAX_VALUE, Long.MAX_VALUE);

    static class Point {
        long y;
        long x;

        Point(long y, long x) {
            this.y = y;
            this.x = x;
        }
    }

    static int solve() {
        for (int i = 0; i < points.size(); i++) {
            if (points.get(i).y < root.y) {
                root = points.get(i);
            } else if (points.get(i).y == root.y) {
                if (points.get(i).x < root.x) {
                    root = points.get(i);
                }
            }
        } // 루트 값은 정함

        Collections.sort(points, (p1, p2) -> {
            int result = ccw(root, p1, p2);

            if (result > 0) {
                return -1;
            } else if (result < 0) {
                return 1;
            } else {
                long dist1 = distance(root, p1);
                long dist2 = distance(root, p2);

                if (dist1 > dist2) {
                    return 1;
                }

                return -1;
            }
        });

        Stack<Point> stack = new Stack<>();
        stack.add(root);

        for (int i = 1; i < points.size(); i++) {
            while (stack.size() > 1 && ccw(stack.get(stack.size() - 2), stack.get(stack.size() - 1), points.get(i)) <= 0) {
                stack.pop();
            }

            stack.add(points.get(i));
        }

        return stack.size();
    }

    static int ccw(Point p1, Point p2, Point p3) {
        long angle = ((p1.x * p2.y) + (p2.x * p3.y) + (p3.x * p1.y))
                - ((p1.y * p2.x) + (p2.y * p3.x) + (p3.y * p1.x));

        return (angle == 0) ? 0
                : (angle > 0) ? 1 : -1;
    }

    static long distance(Point p1, Point p2) {
        return ((p2.y - p1.y) * (p2.y - p1.y)) + ((p2.x - p1.x) * (p2.x - p1.x));
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String, Integer> fun = Integer::parseInt;

        int N = fun.apply(br.readLine());

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            int a = fun.apply(input[0]);
            int b = fun.apply(input[1]);

            points.add(new Point(a, b));
        }

        System.out.println(solve());
    }
}

---

💡 마무리

처음에는 직관적으로 이해하기 어려웠지만,
핵심은 단 하나였다.

"항상 좌회전만 허용한다."

이 원리만 이해하면
Graham Scan은 굉장히 우아한 알고리즘이라는 것을 느낄 수 있다.

기하 문제 중에서도 구조를 이해하는 재미가 있는 문제였다.