[UCPC 2019] 이사 풀이

문제는 여기에서 확인할 수 있다.

---

가장 가까운 점까지의 거리를 $D_{min}$, 가장 먼 점 까지의 거리를 $D_{max}$라 하자.

최소화 하고 싶은 것은 $\frac{D_{min} + D_{max}}{2}$이므로, $D_{min} + D_{max}$의 값을 최소화하면 된다.

어떤 점에 대해서 두 점 $A$, $B$까지의 거리의 합을 최소화 시키려면, 선분 $AB$위에 점이 놓여 있으면 된다.

그리고 $A$가 가장 가까운 점, $B$가 가장 먼 점이 될 가능성을 높이려면, 어떤 점은 $A$위에 놓여있으면 된다.

이런 관찰을 하고 나면, 나머지는 완전 탐색을 통해서 주어진 조건을 만족하는 점을 손쉽게 찾을 수 있다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define ioinit() ios::sync_with_stdio(false), cin.tie(nullptr);
#define INF INT_MAX
 
int N;
int X[1005], Y[1005];
int D[1005][2];
 
inline int distance(int x, int y, int i) {
    return (x-X[i])*(x-X[i]) + (y-Y[i])*(y-Y[i]);
}
 
int main() {
    ioinit();
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> X[i] >> Y[i];
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) continue;
            if (D[i][0] < distance(X[i], Y[i], j)) {
                D[i][0] = distance(X[i], Y[i], j);
                D[i][1] = j;
            }
        }
    }
    int rst = 0, min = INF;
    
    for (int i = 0; i < N; i++) {
        if (min > D[i][0]) {
            min = D[i][0];
            rst = i;
        }
    }
    
    cout << X[rst] << ' ' << Y[rst];
    
    
    return 0;
}