[백준 17371] 이사 (C#, C++) - soo:bak

문제 링크

17371번 - 이사

설명

N개의 편의시설 좌표가 주어질 때, 집을 어디에 두면 가장 가까운 시설과 가장 먼 시설까지 거리 합의 평균이 최소가 되는지 구하는 문제입니다.

접근법

먼저, 최적의 집 위치가 반드시 입력으로 주어진 시설 중 하나임을 알 수 있습니다. 삼각 부등식에 의해, 임의의 위치에 집을 둘 때의 비용은 그 위치에서 가장 가까운 시설에 집을 둘 때의 비용보다 항상 크거나 같기 때문입니다.

다음으로, 집을 시설 위치에 두면 가장 가까운 거리는 0이 됩니다. 따라서 비용 함수는 해당 시설에서 다른 시설까지의 최대 거리로 단순화됩니다.

이후, 모든 시설에 대해 다른 시설까지의 최대 거리를 구하고, 그 값이 가장 작은 시설을 선택합니다. 거리 비교 시 제곱 값을 사용하면 제곱근 연산을 피할 수 있습니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var x = new int[n];
      var y = new int[n];
      for (var i = 0; i < n; i++) {
        var s = Console.ReadLine()!.Split();
        x[i] = int.Parse(s[0]);
        y[i] = int.Parse(s[1]);
      }

      var bestVal = double.MaxValue;
      var bestIdx = 0;

      for (var i = 0; i < n; i++) {
        var maxDist2 = 0.0;
        for (var j = 0; j < n; j++) {
          var dx = (double)(x[i] - x[j]);
          var dy = (double)(y[i] - y[j]);
          var d2 = dx * dx + dy * dy;
          if (d2 > maxDist2)
            maxDist2 = d2;
        }
        if (maxDist2 < bestVal) {
          bestVal = maxDist2;
          bestIdx = i;
        }
      }

      Console.WriteLine($"{x[bestIdx]:0.############} {y[bestIdx]:0.############}");
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  
  vi x(n), y(n);
  for (int i = 0; i < n; i++)
    cin >> x[i] >> y[i];

  double bestVal = numeric_limits<double>::max();
  int bestIdx = 0;

  for (int i = 0; i < n; i++) {
    double maxD2 = 0;
    for (int j = 0; j < n; j++) {
      double dx = x[i] - x[j];
      double dy = y[i] - y[j];
      double d2 = dx * dx + dy * dy;
      if (d2 > maxD2)
        maxD2 = d2;
    }
    if (maxD2 < bestVal) {
      bestVal = maxD2;
      bestIdx = i;
    }
  }

  cout << fixed << setprecision(12);
  cout << x[bestIdx] << " " << y[bestIdx] << "\n";

  return 0;
}