070.md

070 - Plant Planning (★4)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::nth_element()
#include <cmath> // std::abs()

int main()
{
	// N 棟の工場
	int N;
	std::cin >> N;

	std::vector<int> X(N), Y(N);
	for (int i = 0; i < N; ++i)
	{
		std::cin >> X[i] >> Y[i];
	}
	
	// 中央値を求める
	// 参考: https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/library-algorithm#4.4-n-%E7%95%AA%E7%9B%AE%E3%81%AB%E5%B0%8F%E3%81%95%E3%81%84%E8%A6%81%E7%B4%A0%E3%82%92%E6%B1%82%E3%82%81%E3%82%8B
	std::nth_element(X.begin(), (X.begin() + N / 2), X.end());
	std::nth_element(Y.begin(), (Y.begin() + N / 2), Y.end());
	
	const int xMedian = X[N / 2];
	const int yMedian = Y[N / 2];

	long long ans = 0;
	
	for (int i = 0; i < N; ++i)
	{
		ans += std::abs(X[i] - xMedian);
		ans += std::abs(Y[i] - yMedian);
	}

	std::cout << ans << '\n';
}