036.md

036 - Max Manhattan Distance (★5)

解答

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

int main()
{
	// N 個の点, Q 個のクエリ
	int N, Q;
	std::cin >> N >> Q;

	std::vector<long long> Xs(N), Ys(N);
	for (int i = 0; i < N; ++i)
	{
		long long X, Y;
		std::cin >> X >> Y;

		// 45 度の回転（√2 倍の拡大を伴う）
		Xs[i] = (X - Y);
		Ys[i] = (X + Y);
	}

	// 各軸における最小値と最大値を求める
	const auto xp = std::minmax_element(Xs.begin(), Xs.end()); // イテレータのペアを返す
	const auto yp = std::minmax_element(Ys.begin(), Ys.end());
	const auto xMin = *xp.first;
	const auto xMax = *xp.second;
	const auto yMin = *yp.first;
	const auto yMax = *yp.second;

	// 各クエリについて
	for (int i = 0; i < Q; ++i)
	{
		int T;
		std::cin >> T;
		--T;

		// チェビシェフ距離の最大値を求める
		const auto x = Xs[T];
		const auto y = Ys[T];
		const auto a = std::abs(x - xMin);
		const auto b = std::abs(x - xMax);
		const auto c = std::abs(y - yMin);
		const auto d = std::abs(y - yMax);

		std::cout << std::max({ a, b, c, d }) << '\n';
	}
}