平和協定

- 和平协定 - 题目描述 - 高桥的世界有N个国家，所有国家之间都在战斗，死伤无数。所以，各国领导人协商后，决定在几个国家之间建立和平协定。 - 各个国家有面积A和人口B两个数据，比如第i个国家的面积是Ai，人口是Bi。两个国家x，y之间的规模差可以用面积差和人口差的乘积来表示，即(Ax-Ay)*(Bx-By)，这个值定义为规模差，请注意这个值可以是负数。 - 和平协定建立时，两个国家规模差太大或者规模差太小关系就会紧张。也就是说，规模差只有在S1以上，S2以下，和平协定才可以建立。那么，如果可以建立协定的两国全部建立协定，请求出总共建立了几个协定？ - 另外，没有两国面积人口完全相同 - 输入格式 - 共N+1行 - 第一行三个整数，分别为高桥世界的国家数N（1≦N≦50，000），建立协定的下限和上限S1、S2（1≦S1≦S2≦50，000） - 之后的N行每行两个整数Ai、Bi，对于每两个国家i、j，Ai≠Aj和Bi≠Bj至少一个成立 - 输出格式 - 一个整数，为和平协定的个数

[problemUrl]: https://atcoder.jp/contests/code-formula-2014-final/tasks/code_formula_2014_final_h 高橋ワールドには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行で出力せよ。出力の末尾には改行をいれること。

3 1 5
1 1
2 2
4 4

2

4 1 100
1 1
1 2
2 1
2 2

1

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

34

### 部分点 この問題には部分点が設定されている。 - $ 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 $ 点となる。 ### Sample Explanation 1 $ 1,\ 2 $番目の国や$ 2,\ 3 $番目の国は協定を結べますが、$ 1,\ 3 $番目の国は規模の違いが$ 9 $となり上限を超えるので、協定が結べません。 ### Sample Explanation 2 $ 1,\ 4 $番目の国のみが協定を結べます。 $ 2,\ 3 $番目の国の規模の違いは負になることに注意してください。