[백준] 14400 - 편의점 2

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

14400번: 편의점 2

 

2차원 평면 상의 점들과의 거리 중 가장 짧은 거리에 있는 좌표를 구하는 문제이다.

그리디 하게 접근하면, 해답은 다음과 같다.

 

x = 주어진 점들 중에서 x좌표의 중간점

y = 주어진 점들 중에서 y좌표의 중간점

 

여기서 중간점이라는 것은 평균이 아니라, n / 2번째에 있는 점의 좌표라는 것이다.

 

따라서 다음과 같이 구현할 수 있다.

 

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

pair<int, int> a[100000];

bool compare(pair<int, int> p1, pair<int, int> p2)
{
	return p1.second < p2.second;
}

int main()
{
	int n;
	cin >> n;
	long long left = 0, right = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	int x = a[n / 2].first;
	sort(a, a + n, compare);
	int y = a[n / 2].second;
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += abs(x - a[i].first) + abs(y - a[i].second);
	}
	cout << ans;
}