백준 13708번 모든 점을 포함하는 원 JAVA 구현해보기

---

```

백준 13708번 모든 점을 포함하는 원 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 13708번 풀이

---

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

13708번: 모든 점을 포함하는 원

 

 

백준 13708번 모든점을 포함하는 원은

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

 

2차원 평면위에 x, y 좌표를 가진 점 N 개가 주어질 때 해당되는 점들을 포함하는 가장 작은 원의 지름을 구하면 되는 문제입니다.

 

 

---

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

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

---

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

 

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

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

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

 

 

import java.awt.*;
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 {

        // 좌표 리스트
        List<Point> pplCoordinates = new ArrayList<>();

        // 좌표의 수
        final int pplSize = Integer.parseInt(br.readLine());

        // pplCoordinates 좌표값 입력
        for (int i = 0; i < pplSize; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            final int x = Integer.parseInt(st.nextToken());
            final int y = Integer.parseInt(st.nextToken());
            Point pt = new Point(x, y);
            pplCoordinates.add(pt);
        }

        // 평균 값
        double xPos = (double) pplCoordinates.stream().map(pt -> pt.x).reduce(0, Integer::sum) / pplSize;
        double yPos = (double) pplCoordinates.stream().map(pt -> pt.y).reduce(0, Integer::sum) / pplSize;

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

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

        System.out.format("%.2f", distance);
    }

    // 빗변 구하기
    static double findHypotenuse(double rhs, double lhs) {
        return (rhs * rhs) + (lhs * lhs);
    }
}

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

 

 

읽어주셔서 감사합니다

 

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

 

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

 

---