AtCoder Regular Contest 047 B - 同一円周上
解法
ある点からのマンハッタン距離が等しい頂点というのは, こんな感じ(◇)の形をしています。
これでは考えにくいので, 45 度回転させるイメージで, 座標 (x, y) を (x+y, x-y) に変換します。
すると, ある点からのマンハッタン距離が等しい頂点は, 変換した座標系では x 軸, y 軸に平行な辺を持つ正方形の上にあることがわかります。
正方形の 1 辺の長さは max(x 座標の最大値(xmax)と最小値(xmin)の差, y 座標の最大値(ymax)と最小値(ymin)の差) で与えることができ, この 1 辺の長さ D を用いると, 正方形の中心の座標は, x 座標は xmin+D/2, xmax-D/2 のいずれか, また y 座標は ymin+D/2, ymax-D/2 のいずれか, と書けるので, これらのうち条件に合うのを探せば良いです。
const int MAXN = 100010; const ll INF = 1ll<<55; ll X[MAXN], Y[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<ll> xm(2), ym(2); xm[0] = INF, xm[1] = -INF, ym[0] = INF, ym[1] = -INF; for (int i = 0; i < N; i++) { cin >> X[i] >> Y[i]; ll x = X[i]+Y[i]; ll y = X[i]-Y[i]; xm[0] = min(x, xm[0]); xm[1] = max(x, xm[1]); ym[0] = min(y, ym[0]); ym[1] = max(y, ym[1]); } ll D = max(xm[1]-xm[0], ym[1]-ym[0])/2; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) { ll x = xm[i]+D*(i==0?1:-1); ll y = ym[j]+D*(j==0?1:-1); ll ax = (x+y)/2, ay = (x-y)/2; ll d = -1; bool ng = false; for (int k = 0; k < N; k++) { ll D = abs(ax-X[k])+abs(ay-Y[k]); if (d != -1 && d != D) ng = true; d = D; } if (!ng) { cout << ax << " " << ay << endl; return 0; } } assert(false); return 0; }