(자바) 백준 7420번 : 맹독 방벽

이거 분명 어디서 본 내용이길래 냅다 시도해봤다. 확인해보니 컨벡스 헐 문제 하나밖에 안풀었더라.. 생각보다 인상깊은 알고리즘이었나보다. 다음주에 도쿄간다... 스키는 탈까 말까 고민중!  탔다가 사고내서 파산하는건 아닐지..
교환학생이 곧 끝나서 지금은 해야할게 많다... 서류많고, 팀플많고, 발표많다...발표준비...🥲

 

---

문제 
 
https://www.acmicpc.net/problem/7420
 
 

문제 이해
 
- 건물들이 주어지고 이 건물들을 포함하는 방벽을 짓는다. → 컨벡스 헐이다.
- 방벽은 건물들과 L 거리 이상 떨어져있어야한다. → 컨벡스 헐 의 결과에서 L 거리씩 넓힌다?
- 방벽의 최소길이는 무엇인가.
 
 
코드 설명
- 초반에 틀린 부분
     1. 컨벡스 헐에서 L 만큼을 x,y에 각각 더하거나 빼서 팽창시킴 → 이렇게 하면 최소 길이보다 더 나옴. → 각 각도에 대한 호를 계산해 더하기만 하면됨..
         

     2. 각도 기준 정렬을 할 때, 기준점과 함께 정렬해버려서 섞임.  → 기준점을 스택에서 제거하고 진행함.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class B_7420 {
    static class Point {
        int x, y;
 
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
 
        static int crossProduct(Point p, Point q, Point r) {
            return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
        }
    }
 
    static int distance(Point p1, Point p2) {
        return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
    }
 
    static List<Point> grahamScan(List<Point> points) {
        if (points.size() < 3)
            return points;
 
        Point start = points.get(0);
        for (Point p : points) {
            if (p.y < start.y || (p.y == start.y && p.x < start.x))
                start = p;
        }
 
        Point finalStart = start;
        points.remove(start);  
 
        points.sort((p1, p2) -> {
            long cp = Point.crossProduct(finalStart,p1,p2);
            if (cp == 0)
                return Long.compare(distance(finalStart, p1), distance(finalStart, p2));
            return cp > 0 ? -1 : 1;
        });
 
        Stack<Point> stack = new Stack<>();
        stack.push(finalStart);
        for (Point p : points) {
            while (stack.size() > 1 && Point.crossProduct(stack.get(stack.size() - 2), stack.peek(), p) <= 0) {
                stack.pop();
            }
            stack.push(p);
        }
        return new ArrayList<>(stack);
    }
 
    static double Line(List<Point> hull) {
        double line = 0;
        int n = hull.size();
        for (int i = 0; i < n; i++) {
            Point a = hull.get(i);
            Point b = hull.get((i + 1) % n);
            double dx = b.x - a.x;
            double dy = b.y - a.y;
            double length = Math.sqrt(dx * dx + dy * dy);
            line += length;
        }
        return line;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
 
        List<Point> points = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            points.add(new Point(x, y));
        }
 
        List<Point> hull = grahamScan(points);
        double straightLength = Line(hull);
        double cornerLength = 2 * Math.PI * L;
 
        System.out.println(Math.round(straightLength + cornerLength));
    }
}