# C - King's Summit [문제 링크](https://atcoder.jp/contests/abc419/tasks/abc419_c) ## Problem Statement There is a grid with $10^9$ rows and $10^9$ columns. Let $(i, j)$ denote the square at the $i$-th row from the top and $j$-th column from the left. There are $N$ people on the grid. Initially, the $i$-th person is at square $(R_i, C_i)$. Time starts at $0$. Each person can do the following move at times $1,2,3,4,\ldots$: - Stay at the current position, or move to an $8$-adjacent square. It is forbidden to leave the grid. Formally, from $(i, j)$ one may move to any of $(i-1,j-1)$, $(i-1,j)$, $(i-1,j+1)$, $(i,j-1)$, $(i,j)$, $(i,j+1)$, $(i+1,j-1)$, $(i+1,j)$, $(i+1,j+1)$ that exists. Assume each move takes no time. Find the minimum possible time when the $N$ people are all at the same square. ## Constraints - $1 \le N \le 2 \times 10^{5}$ - $1 \le R_i, C_i \le 10^{9}$ - All input values are integers. ## Input The input is given in the following format: $N$ $R_1\ C_1$ $R_2\ C_2$ $\vdots$ $R_N\ C_N$ ## Output Output the answer. ## 풀이 #### R과 C 각각의 최대 최소를 기록하여 중앙으로 이동하였다. ``` c++ #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int minR=INT_MAX, maxR=INT_MIN, minC=INT_MAX, maxC=INT_MIN; while(n--) { int r, c; cin >> r >> c; minR = min(minR, r); maxR = max(maxR, r); minC = min(minC, c); maxC = max(maxC, c); } cout << max((maxR-minR+1)/2, (maxC-minC+1)/2); } ```