C++ [BOJ] 백준 17371번 이사

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

17371번: 이사

---

SOLUTION

처음에 티어랑 문제 보고 어려운 알고리즘 문제인 줄 알았다.

 

문제 풀이 방향 잡기가 어려웠는데, 그냥 주어진 편의시설 좌표들을 N^2으로 돌아서 특정한 점으로부터 다른 점까지의 거리의 최댓값이 최소가 되는 경우를 찾으니까 예제 출력이랑은 다른데 답이 맞았다.

 

스페셜저지 문제 가끔 당황스럽다..

---

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<pair<int, int>>v;

double euclideanDistance(int x1, int y1, int x2, int y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n;i++) {
		int x, y;
		cin >> x >> y;
		v.push_back({ x,y });
	}
	int idx;
	double mindis = INFINITY;
	for (int i = 0; i < n; i++) {
		double maxdis = -INFINITY;
		for (int j = 0; j < n; j++) {
			if (maxdis < euclideanDistance(v[i].first, v[i].second, v[j].first, v[j].second))
				maxdis = euclideanDistance(v[i].first, v[i].second, v[j].first, v[j].second);
		}
		if (mindis > maxdis) {
			mindis = maxdis;
			idx = i;
		}
	}
	cout << v[idx].first << ' ' << v[idx].second;
}