Hide

Problem M
マンハッタンの朝

Languages en ja
/problems/manhattanmornings/file/statement/ja/img-0001.jpg

ニューヨーカーであるあなたはいつも忙しい。というのも、仕事とは別に、毎日の多くの用事を済まさなければならないからだ。あなたは早起きが嫌いなので用事をいつも仕事の後で行っているが、そのせいで自分の時間がなくなってしまう。

ある日、あなたは用事を行う場所が通勤経路にあることに気づき、それなら仕事前に寄っていけばいいと思った。さらに翌日には、通勤経路を少し変えれば距離を変えずにより多くの場所を通ることができることに気づいた。用事を済ますにはほとんど時間がかからないので、それなら今までと同じ時間に起きることができる! ニューヨークの道路は格子状になっており、好きな経路を通ることができる。早起きせずに、与えられた場所をどれだけ多く通ることができるだろうか。

ニューヨークの道路は、$x$軸に平行な道路と$y$軸に平行な道路としてモデル化できる。 具体的には、任意の$a\in \mathbb Z$ に対して $y=a$ となる道と、任意の任意の $b\in \mathbb Z$ に対して $x=b$ となる道がある。用事を行う場所は、必ず道路の交点にある。また、すべての道路は任意の方向に通ることができる。

入力

  • 先頭行は $0\leq n\leq 10^5$ の整数で、その日に行う用事の数を表す。

  • 次の行は $0\leq x_ h, y_ h, x_ w, y_ w\leq 10^9$$4$つの整数で、あなたの家および職場の位置を表す。

  • それ以降の $n$ 行は $0\leq x_ i,y_ i\leq 10^9$$2$つの整数で、 $i$番目の用事を行う場所の位置を表す。

出力

出力は単一行で、家から職場までに必要な距離を超えずに通ることができる最大の用事の場所の数を含む。

サンプル入力 1 サンプル出力 1
3
0 0 6 6
5 4
2 6
3 1
2
サンプル入力 2 サンプル出力 2
5
2 1 0 0
0 0
0 1
2 0
2 1
3 1
3
サンプル入力 3 サンプル出力 3
4
200 100 100 200
50 150
200 200
100 100
100 100
2