← 返回题目列表

Codeforces · 592/E

E. BCPC编程赛

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

BCPC 代表 Byteforces 大学编程竞赛,是 Byteforces 中最著名的竞赛。

BCPC 是一项团体赛。每队由一名教练和三名选手组成。 Blenda是比特州立大学(BSU)的教练,她对队员的选拔非常严格。

BSU 有 n 名学生,编号从 1 到 n。由于所有 BSU 学生都非常聪明,因此 Blenda 唯一重要的参数是他们的读写速度。经过仔细测量,布兰达发现第 i 个学生的阅读速度等于 ri(每分钟单词数),写作速度等于 wi(每分钟符号数)。由于 BSU 学生非常聪明,测量的速度有时非常大,Blenda 决定从所有阅读速度值中减去一些常数值 c,并从所有写入速度值中减去一些值 d。因此她认为 ri' = ri - c 且 wi' = wi - d。

当且仅当 ri'·wj' > rj'·wi' 时,学生 i 被称为压倒学生 j。 Blenda 不喜欢团队打架,所以她认为由三个不同的学生 i、j 和 k 组成的团队是好的,如果 i 压倒 j、j 压倒 k、k 压倒 i。是的,压倒性的关系不是传递性的,因为它在现实生活中经常发生。

由于 Blenda 正忙于准备 Codeforces 的训练营,因此您需要计算 BSU 中不同优秀团队的数量。如果至少有一名学生出现在一个团队中但没有出现在另一团队中,则两个团队被视为不同。换句话说,如果组成这两个团队的学生组不同,那么这两个团队就是不同的。

输入

在输入的第一行写入三个整数n、c和d(3≤n≤345678、1≤c、d≤109)。它们分别表示 Blenda 可以用来组成团队的学生人数、从所有阅读速度中减去的值以及从所有书写速度中减去的值。

接下来的 n 行每行包含两个整数 ri 和 wi (0 < ri, wi ≤ 109, |ri - c| + |wi - d| > 0)。不存在两个学生的阅读和写作速度一致,即对于每个 i ≠ j 条件 |ri - rj| + |wi - wj| > 0 成立。

输出

打印 BSU 中不同团队的数量,根据 Blenda 的定义,这些团队的数量是良好的。

示例

输入 #1

5 2 2
1 1
4 1
2 3
3 2
3 4

输出 #1

4

输入 #2

7 6 6
3 2
1 7
5 7
3 7
6 4
8 9
8 5

输出 #2

11

注意

在第一个样本中,以下团队表现较好:(i = 1, j = 2, k = 3)、(i = 2, j = 5, k = 1)、(i = 1, j = 4, k = 3)、(i = 5, j = 1, k = 4)。

请注意,例如团队 (i = 3, j = 1, k = 2) 也不错,但被认为与团队 (i = 1, j = 2, k = 3) 相同。