ABC178 E - Dist Max (500)
最初の考察
CodeRunnerか何かで適当な点から一番遠い点とそこから一番遠い点が最大距離とかやっていたので実装しWA
次の考察
マンハッタン距離の計算方法を考えると$ x-y、$ x+y、ついでにx軸、Y軸でソートしてそれぞれで一番遠いものの距離が答えになりそう
$ x-y、$ x+yでソートする方針は合っていたが、0番目と1番目の要素を比較していたためWA
コンテスト後に修正したらAC
最終的な考察
点をx軸で昇順にソート
すると$ i \lt jで$ A_i \lt A_jになるのでマンハッタン距離は$ (x_j - x_i) + |y_i - y_j|
Setを2種類用意する
$ x_j + y_jでソートするSetと$ x_j - y_jでソートするSet
前のは自身よりY座標が大きいものを後のは小さいものを得るために使う
それぞれの座標で以下のとおりにする
二種類のSetから最も遠い点をそれぞれ取得する
大きい方のマンハッタン距離と最大値で比較して更新する
それぞれのSetから自身の点を削除する
同じ座標に点がある場合、上の動作の前にSetが空で無いことを確認する必要がある
ソートがボトルネックで$ O(N \log N)