Time Limit: 4 sec / Memory Limit: 64 MB
問題文
高橋ワールドにはN個の国が存在します。現在はどの国も互いにいがみ合っており、殺伐としています。 そこで各国の首脳が話し合って、いくつかの国の間で平和協定を結ぶことにしました。
各国には面積と人口の2つのパラメーターが有り、 i 番目の国の面積は A_i、 人口は B_i です。 ある2つの国 x, y に対して、面積の差と人口の差の積、つまり (A_x - A_y) ×(B_x - B_y) の値を「規模の違い」と定義します。これが負になることがあることに注意してください。
平和協定は2国間で結ばれますが、規模が違いすぎたり、似すぎたりすると関係がうまくいかないので、ほどよく規模が違う国同士でのみ協定を結びます。 すなわち「規模の違い」がS1以上、S2以下であるような場合のみ、その2国は協定を結ぶことができます。 もし仮に、協定を結ぶことが出来る2国が全て協定を結んだ場合、何個の協定が結ばれるか求めてください。
なお、面積も人口も全く同じであるような2国は存在しません。
入力
入力は以下の形式で標準入力から与えられる。
N S1 S2 A_1 B_1 A_2 B_2 : A_N B_N
- 1 行目には高橋ワールドにある国の数N(1 ≦ N ≦ 50,000)、協定を結ぶための「規模の違い」の下限と上限S1, S2(1 ≦ S1 ≦ S2 ≦ 50,000)が空白区切りで与えられる。
- 2 行目からの N 行のうち i 行目には i 番目の国の面積 A_i(1 ≦ A_i ≦ 50,000) と人口 B_i(1 ≦ B_i ≦ 50,000) が空白区切りで与えられる。
- i ≠ j ならば A_i ≠ A_j と B_i ≠ B_j の少なくとも一方が成立する。
部分点
この問題には部分点が設定されている。
- 1 ≦ N ≦ 3,000 ,1 ≦ S1 ≦ S2 ≦ 3,000 , 1 ≦ A_i, B_i ≦ 3,000 を満たすデータセットに正解した場合は 10 点が与えられる。
- 1 ≦ N ≦ 50,000 ,1 ≦ S1 ≦ S2 ≦ 50,000 , 1 ≦ A_i, B_i ≦ 50,000 を満たすデータセットに正解した場合はさらに 90 点が与えられる。合計で 100 点となる。
出力
協定を結べる国が全て協定を結んだ場合に、結ばれる協定の個数を1行で出力せよ。出力の末尾には改行をいれること。
入力例1
3 1 5 1 1 2 2 4 4
出力例1
2
1, 2番目の国や2, 3番目の国は協定を結べますが、1, 3番目の国は規模の違いが9となり上限を超えるので、協定が結べません。
入力例2
4 1 100 1 1 1 2 2 1 2 2
出力例2
1
1, 4番目の国のみが協定を結べます。 2, 3番目の国の規模の違いは負になることに注意してください。
入力例3
16 3 14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5
出力例3
34