[백준] 17371번 이사

문제 설명

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

문제 풀이

• 그리디한 방식으로 BruteForce를 진행하면 된다.
• 문제에서 가장가까운 거리, 가장 먼 거리의 평균을 구한다고 했는데 편의시설 지점을 정답 후보로 두게되면 가장가까운 거리는 0으로 소거가 가능하여 현재 노드에서 가장 먼 거리의 노드까지 거리가 가장 작은 노드를 구하면 된다.
• 이중 for문으로 간단하게 풀이가 가능하다. O(n^2)

소스 코드 (JAVA)

import java.io.*;
import java.util.*;
import java.util.List;

class Main {

    static BufferedReader br;
    static BufferedWriter bw;

    static class Point {
        int x, y;

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

    static int N;
    static List<Point> arr = new ArrayList<>();

    static void solve() throws IOException {
        int minInd = -1;
        double minVal = Double.MAX_VALUE;

        for (int i = 0; i < arr.size(); i++) {
            double maxVal = 0;
            for (int j = 0; j < arr.size(); j++) {
                if (i == j) continue;
                Point A = arr.get(i);
                Point B = arr.get(j);
                double dist = Math.sqrt(Math.pow(Math.abs(A.x - B.x), 2) + Math.pow(Math.abs(A.y - B.y), 2));
                maxVal = Math.max(maxVal, dist);
            }
            if (maxVal < minVal) {
                minInd = i;
                minVal = maxVal;
            }
        }
        bw.write(arr.get(minInd).x + " " + arr.get(minInd).y + "\n");
    }

    static void input() throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        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());
            arr.add(new Point(x, y));
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bw.flush();
    }
}