17371 이사

이런 문제가 기하인가? 원 공식이랑 비슷하니 원을 사용하나? 고민 많이 했는데 그리디 문제였다. 길이의 평균을 구하는 거라 집이 편의점 위에 가도 값의 차이는 없다. 그래서 편의점 사이의 거리가 가장 짧은 걸 구하면 된다.

 

어렵지는 않은데 자꾸 잠이 와서 정신을 못차리겠다. 가장 긴 길이 구하기 -> 긴 길이가 최소가 되면 저장 이렇게 쭉쭉 풀면 되는데 자꾸 멍해져서 엄청 틀렸다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#pragma warning(disable:4996)

using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int len(int x1, int x2, int y1, int y2)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

int main() {
    int n;
    scanf("%d", &n);

    vector<ii> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &v[i].xx, &v[i].yy);

    int min = 999999999;
    int mini = 0;

    for (int i = 0; i < n; i++)
    {
        int max = -1;
        int maxi = i;
        for (int j = 0; j < n; j++)
        {
            if (j == i)
                continue;

            if (max < len(v[i].xx, v[j].xx, v[i].yy, v[j].yy))
            {
                max = len(v[i].xx, v[j].xx, v[i].yy, v[j].yy);
                maxi = i;
            }
        }

        if (min > max)
        {
            min = max;
            mini = maxi;
        }
    }

    cout << v[mini].xx << " " << v[mini].yy << endl;

    return 0;
}