AGC019 C Fountain Walk - 足跡-sokuseki-

問題概要

東西方向と南北方向にそれぞれ $10^8$ 本の道路があり、となりあう道路間の距離は $100$ メートルである。すべての東西方向の道路はすべての南北方向の道路と直交し、すべての交差点は、交差する南北方向の通りの番号を $x$ 、東西方向の通りの番号を $y$ として組 ( $x$ , $y$ ) で表される。

$N$ 個の噴水があり、 $i$ 番目の噴水は交差点( $X_i$ , $Y_i$ )に設置されている。
噴水がある交差点には、交差点を中心とした半径 $10$ メートルの円が噴水の外周として描かれており、その内部に道路はない。

交差点( $x_1$ , $y_1$ )から交差点( $x_2$ , $y_2$ )に移動するのに歩く最短距離を求めよ。

制約

$1 \le N \le 200,000$
$0 \le x_1, y_1, x_2, y_2 \le 10^8$
$0 \le X_i, Y_i \le 10^8$
$i \neq j$ のとき $X_i \neq X_j$
$i \neq j$ のとき $Y_i \neq Y_j$
交差点( $x_1$ , $y_1$ ) , ( $x_2$ , $y_2$ ) は異なり、どちらも噴水は設置されていない

解法

交差点で曲がるときは、噴水のある交差点で曲がる方が歩く距離は短くすむ。
交差点で曲がらない場合は噴水がない方が距離は短くすむ。

よって、( $x_1$ , $y_1$ ) から ( $x_2$ , $y_2$ )に向かうときに、できるだけ噴水のある交差点を通りながら曲がりたい気持ちになる。
このとき、経由する噴水の数を最大化すると最短距離となるので、噴水の最大の数を求めたい。

簡単のため、( $x_1$ , $y_1$ ) が左下、 ( $x_2$ , $y_2$ )が右上にあるとすると、右方向と上方向の移動だけ考えればよい。
よって最短距離に関係のある噴水は、( $x_1$ , $y_1$ ) を左下、 ( $x_2$ , $y_2$ )を右上とする長方形領域に含まれる噴水のみである。

長方形の左下から右上に移動する際に経由できる噴水に最大数は、噴水の座標の集合をx座標でソートして、y座標でLISを求めてあげるとよい。（制約よりx座標やy座標が等しくなる噴水は存在しないので、特別な処理はいらない）
よって、噴水がない場合の( $x_1$ , $y_1$ ) から ( $x_2$ , $y_2$ ) への最短距離から、LIS の数だけ噴水を経由する距離を引いてあげ得ると答えがでる。（ $x_1 = x_2$ または $y_1 = y_2$ で、長方形領域（実際は直線）に噴水が含まれる場合に注意する）

LISを求めるのは $O(N log N)$ でできるので、全体の計算量は $O(N log N)$ となる。

Submission #2866777 - AtCoder Grand Contest 019