백준 11930번 Smallest Enclosing Sphere 구현해보기

---

```

백준 11930번 Smallest Enclosing Sphere 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 11930번 풀이

---

https://www.acmicpc.net/problem/11930

11930번: Smallest Enclosing Sphere

 

백준 11930번 Smallest Enclosing Sphere는

난이도 플래티넘 등급의 문제로서

 

N 개의 3차원 점이 주어질 때

해당되는 점들을 포함하는 가장 작은 구를 구해주면 되는 문제입니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

저는 Gradient Decent 알고리즘을 사용하여서 해당 문제를 풀었습니다.

 

 

풀이는 아래 문제를 참조해주시면 됩니다.

2389번은 2차원 점을 구하는 문제입니다.

https://codemasterkimc.tistory.com/319?category=952166

백준 2389번 세상의 중심에서... JAVA 구현해보기

 

해당 문제는 3차원이기 때문에

빗변을 x^2+y^2+z^2를 이용해서 구해주면 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        final int coordinateNum = Integer.parseInt(br.readLine());
        sb.append(findRadius(coordinateNum));
        System.out.println(sb);
    }

    static String findRadius(int cn) throws IOException {
        // 좌표 리스트
        List<Point3D> pplCoordinates = new ArrayList<>();

        // pplCoordinates 좌표값 입력
        for (int i = 0; i < cn; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            final double x = Double.parseDouble(st.nextToken());
            final double y = Double.parseDouble(st.nextToken());
            final double z = Double.parseDouble(st.nextToken());
            Point3D pt = new Point3D(x, y, z);
            pplCoordinates.add(pt);
        }

        // 평균 값
        double xPos = pplCoordinates.stream().map(pt -> pt.x).reduce(0.0, Double::sum) / cn;
        double yPos = pplCoordinates.stream().map(pt -> pt.y).reduce(0.0, Double::sum) / cn;
        double zPos = pplCoordinates.stream().map(pt -> pt.y).reduce(0.0, Double::sum) / cn;

        // 보정값
        double precision = 0.1;
        // 반지름의 제곱
        double distance = 0;
        // 반복횟수는 다다익선
        for (int i = 0; i < 25000; i++) {
            int idx = 0;
            distance = find3DHypotenuse(xPos - pplCoordinates.get(0).getX(), yPos - pplCoordinates.get(0).getY(), zPos - pplCoordinates.get(0).getZ());
            for (int j = 1; j < cn; j++) {
                final double possibleDistance = find3DHypotenuse(xPos - pplCoordinates.get(j).getX(), yPos - pplCoordinates.get(j).getY(), zPos - pplCoordinates.get(j).getZ());
                // 길이 비교를 해서 클경우 새로운 빗변으로 변경
                // 보정할때 비교할 좌표 변경
                if (distance < possibleDistance) {
                    distance = possibleDistance;
                    idx = j;
                }
            }
            // 길이보정해주기
            xPos += (pplCoordinates.get(idx).getX() - xPos) * precision;
            yPos += (pplCoordinates.get(idx).getY() - yPos) * precision;
            zPos += (pplCoordinates.get(idx).getZ() - zPos) * precision;
            precision *= 0.999;
        }

        distance = ((double) Math.round(Math.sqrt(distance) * 100) / 100);

        return String.format("%.2f", distance);
    }

    // 빗변 구하기
    static double find3DHypotenuse(double x, double y, double z) {
        return (x * x) + (y * y) + (z * z);
    }

    // 문제가 아닌 일반 코드의 경우 외부파일
    // 3D domain
    private static class Point3D {
        private final double x;
        private final double y;
        private final double z;

        public Point3D(double x, double y, double z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        public double getX() {
            return x;
        }

        public double getY() {
            return y;
        }

        public double getZ() {
            return z;
        }
    }
}

//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---