各クエリにおいて, 神社を先に行く移動の順は以下の4通りである.

  • 出発地, そこから東側に一番近い神社, そこから東側に一番近い寺
  • 出発地, そこから東側に一番近い神社, そこから西側に一番近い寺
  • 出発地, そこから西側に一番近い神社, そこから東側に一番近い寺
  • 出発地, そこから西側に一番近い神社, そこから西側に一番近い寺

これらをすべて計算して一番移動距離が小さいものを探す.

寺を先に行く移動も同様に計算して, 小さい方の移動距離が答えとなる.

一番近い○○を求めるには二分探索を使う.