CF592E.BCPC

省选/NOI-

通过率:0%

时间限制:4.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

BCPC stands for Byteforces Collegiate Programming Contest, and is the most famous competition in Byteforces.

BCPC is a team competition. Each team is composed by a coach and three contestants. Blenda is the coach of the Bit State University(BSU), and she is very strict selecting the members of her team.

In BSU there are n students numbered from 1 to n. Since all BSU students are infinitely smart, the only important parameters for Blenda are their reading and writing speed. After a careful measuring, Blenda have found that the i-th student have a reading speed equal to r__i (words per minute), and a writing speed of w__i (symbols per minute). Since BSU students are very smart, the measured speeds are sometimes very big and Blenda have decided to subtract some constant value c from all the values of reading speed and some value d from all the values of writing speed. Therefore she considers r__i' = r__i - c and w__i' = w__i - d.

The student i is said to overwhelm the student j if and only if r__i'·w__j' > r__j'·w__i'. Blenda doesn’t like fights in teams, so she thinks that a team consisting of three distinct students i, j and k is good if i overwhelms j, j overwhelms k, and k overwhelms i. Yes, the relation of overwhelming is not transitive as it often happens in real life.

Since Blenda is busy preparing a training camp in Codeforces, you are given a task to calculate the number of different good teams in BSU. Two teams are considered to be different if there is at least one student that is present in one team but is not present in the other. In other words, two teams are different if the sets of students that form these teams are different.

BCPC 代表 Byteforces 大学编程竞赛(Byteforces Collegiate Programming Contest),是 Byteforces 最著名的赛事。

BCPC 是一项团队赛。每支队伍由一名教练和三名参赛选手组成。布伦达(Blenda)是比特州立大学(Bit State University,BSU)的教练,她在挑选自己队伍的队员时非常严格。

BSU 共有 $ n $ 名学生,编号从 $ 1 $ 到 $ n $。由于所有 BSU 学生都极其聪明,对布伦达而言,唯一重要的参数是他们的阅读速度与写作速度。经过仔细测量,布伦达发现第 $ i $ 名学生的阅读速度为 $ r_i $(单位:词/分钟),写作速度为 $ w_i $(单位:符号/分钟)。由于 BSU 学生极其聪明,测得的速度有时非常大,因此布伦达决定从所有阅读速度值中减去某个常数 $ c $,并从所有写作速度值中减去某个常数 $ d $。于是她定义修正后的速度为 $ r_i' = r_i - c $ 和 $ w_i' = w_i - d $。

当且仅当 $ r_i' \cdot w_j' > r_j' \cdot w_i' $ 时,称学生 $ i $ 压制(overwhelm)学生 $ j $。布伦达不喜欢队内出现矛盾,因此她认为一支由三名互不相同的同学 $ i 、、 j 、、 k $ 组成的队伍是好队伍(good team),当且仅当 $ i $ 压制 $ j 、、 j $ 压制 $ k $,且 $ k $ 压制 $ i $。没错,这种“压制”关系并不具有传递性——这在现实生活中也常常发生。

由于布伦达正忙于在 Codeforces 上筹备训练营,现交由你来计算 BSU 中不同好队伍的数量。若两支队伍中至少存在一名学生只属于其中一支队伍,则认为这两支队伍不同。换言之,若构成两支队伍的学生集合不同,则这两支队伍即被视为不同。

输入格式

In the first line of the input three integers n, c and d (3 ≤ n ≤ 345678, 1 ≤ c, d ≤ 109) are written. They denote the number of students Blenda can use to form teams, the value subtracted from all reading speeds and the value subtracted from all writing speeds respectively.

Each of the next n lines contains two integers r__i and w__i (0 < r__i, w__i ≤ 109, |r__i - c| + |w__i - d| > 0). There are no two students, such that both their reading and writing speeds coincide, i.e. for every i ≠ j condition |r__i - r__j| + |w__i - w__j| > 0 holds.

输入的第一行包含三个整数 nn、cc 和 dd(3≤n≤3456783 \leq n \leq 345678,1≤c,d≤1091 \leq c, d \leq 10^9),分别表示布琳达可用于组队的学生人数、从所有阅读速度中减去的值、以及从所有写作速度中减去的值。

接下来的 nn 行,每行包含两个整数 rir_i 和 wiw_i(0<ri,wi≤1090 < r_i, w_i \leq 10^9,且 ∣ri−c∣+∣wi−d∣>0|r_i - c| + |w_i - d| > 0)。不存在两名学生,其阅读速度与写作速度均相同;即对任意 i≠ji \neq j,均有 ∣ri−rj∣+∣wi−wj∣>0|r_i - r_j| + |w_i - w_j| > 0。

输出格式

Print the number of different teams in BSU, that are good according to Blenda's definition.

输出 BSU 中符合布伦达定义的“优秀”队伍的不同数量。

输入输出样例

  • 输入#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

说明/提示

In the first sample the following teams are good: (i = 1, j = 2, k = 3), (i = 2, j = 5, k = 1), (i = 1, j = 4, k = 3), (i = 5, j = 1, k = 4).

Note, that for example the team (i = 3, j = 1, k = 2) is also good, but is considered to be the same as the team (i = 1, j = 2, k = 3).

在第一个样例中,以下队伍是优秀的:(i=1, j=2, k=3)(i=1,\,j=2,\,k=3)、(i=2, j=5, k=1)(i=2,\,j=5,\,k=1)、(i=1, j=4, k=3)(i=1,\,j=4,\,k=3)、(i=5, j=1, k=4)(i=5,\,j=1,\,k=4)。

注意,例如队伍 (i=3, j=1, k=2)(i=3,\,j=1,\,k=2) 同样是优秀的,但被视为与队伍 (i=1, j=2, k=3)(i=1,\,j=2,\,k=3) 相同。

输入解题思路,AI测评打分。不知道怎么写?

首页