問題文
高桥世界有N个国家。当前,各国都在互相争斗、互相残杀。 于是各国领导人商议,决定缔结几个国家之间的和平协议。
每个国家都有两个参数:面积和人口。 i 国家的面积是 A_i,人口为 B_i 。 两个国家 对于 x, y ,面积差和人口差的乘积,即 将 (A_x - A_y) ×(B_x - B_y) 的值定义为“比例差异”。请注意,这可能是负数。
和平协议是在两个国家之间签订的,但如果规模相差太大或太相似,关系就不会很好,所以协议只在规模相差不大的国家之间签订。 换句话说,就是“规模差异”S1以上、S2两个国家只有在以下情况下才可以签订协议: 如果所有能达成协议的国家都达成协议,求将达成多少个协议。
请注意,没有两个国家拥有完全相同的面积和人口。
入力
输入是按以下格式从标准输入给出的。
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
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