Back to : algorithms
  • 난이도 : Gold 2
  • 출처 : UCPC 2019 인터넷 예선 J번
  • solved ac class 6 essential

풀이

주어진 점들 중 하나가 반드시 답이 됨을 보이자.

먼저, 평균을 최소화하는 대신 합을 최소화하는 것으로 생각하자. 답이 되는 점이 $X$ 라고 하고, 주어진 점들 중 $X$에 가장 가까운 점을 $A$, 가장 먼 점을 $B$라고 하자. 이때, 우리가 최소화하는 것은 $\overline{XA} + \overline{XB}$ 이다. 이때, 삼각 부등식으로부터 이 값이 $\overline{AB}$보다 크거나 같기 때문에, $X$ 대신 $A$를 택함으로써 반드시 거리의 합 상 이득을 얻게 된다. 따라서, 반드시 주어진 점들 중 하나가 답이 된다.

Code

#include <bits/stdc++.h>
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

struct pt
{
    double x, y;
    double dt(pt &o)
    {
        return sqrt((x-o.x)*(x-o.x) + (y-o.y)*(y-o.y));
    }
};

pt pts[1010];
int32_t main()
{
    usecppio
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        double x, y; cin >> x >> y;
        pts[i] = {x, y};
    }
    int best = -1;
    double score = 1e12;
    for (int i = 1; i <= n; i++)
    {
        double MD = 0;
        for (int j = 1; j <= n; j++)
            MD = max(MD, pts[i].dt(pts[j]));
        double sc = MD / 2;
        if (score >= sc)
        {
            score = sc;
            best = i;
        }
    }
    cout << pts[best].x << ' ' << pts[best].y << '\n';
}