ARC047 B. 同一円周上
問題
座標平面上にN個の点がある。
各点の座標は整数で、ある点Pとのマンハッタン距離が同じであることがわかっている。(点Pの座標も整数)
点Pとしてあり得る点を一つ出力せよ。
制約
1 <= N <= 10^5
-10^9 <= x,y <= 10^9
解説
平面座標で、点Pからのマンハッタン距離が同じ点というのは、点Pを中心とするひし形の線上に乗る。
しかし、ひし形のまま扱うのは大変なので、テクニックとして45度回転させた座標を考える。
(x,y)->(x+y,x-y)という変換を考えると、上記の「ひし形の線上」というのが「正方形の線上」になり、とても考えやすい。
また、平面座標のどこかの候補点を探す場合、かつ、単純な方法では候補点が多くなりすぎる場合は、候補点を絞ることを考える。
(x座標・y座標それぞれで、線分の端点や交点などだけ取り出してその組み合わせを考える、など)
今回の場合、正方形の1辺の長さDが決まれば、点Pの座標は各点から距離Dの点のどこかということになる。(これだけだとまだ候補点が多すぎる)
もし正方形の1辺が決まれば、その辺の端点から距離がD/2の点(辺に対して両側が考えれる)が候補点になる。
そこで、正方形の辺を探す。
変換後の平面座標において、各軸について独立に出現している点の座標を考える。
その座標で最小の点と最大の点を見つける。
このとき、これらの点を端点とする辺が「正方形の1辺」の候補になる。
(例外としてN=1の時は1辺が作れないので別処理する)
これより長い辺を考える必要があるかというと、もう片方の軸の方で同じことをして見つけた辺がより長い場合、そちらが1辺の長さとしてふさわしい。
言い換えると、各軸について辺の長さを求めて、その大きな方が正方形の1辺の長さDとしてふさわしい。
(Dも候補として各軸について求めた2つがあると考えてもよい)
そして、候補点はそれぞれの点からD/2だけずれた点となる。(最大点+D/2,最大点-D/2,最小点+D/2,最小点-D/2の4点 最大点-D/2,最小点+D/2の2つ)
あとは候補点すべてについて実際に成り立つ点Pを確認してあげればよい。
計算量は、候補点の組み合わせで4*4=16個2*2=4個(または、各軸のDの候補を別に考える場合は、8*8=64個 4*4=16個)についてO(N)でチェックすることになるので、間に合う。
反省
- 座標系で絶対値が出てきたら45度回転させてみる
- 候補点が無数に考えられる場合、端点や中点など候補点としてありえる部分に絞って探索する
