← 返回题目列表

AtCoder · code_formula_2014_final_h

H. 和平协议

中文机器翻译题面 查看原题

問題文

高桥世界有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