P3114 [USACO15JAN] Stampede S

题目描述

FJ 的 $N$ 头奶牛（$1 \leq N \leq 50,000$）看似在农场前的路上狂奔，实际上它们正在进行一场赛跑。

从上方俯视，每头牛在时间 $t = 0$ 时被表示为一个单位长度的水平线段，其左端点坐标为 $(x, y)$。例如，$(-3, 6)$ 表示一头在 $t = 0$ 时从 $(-3, 6)$ 延伸到 $(-2, 6)$ 的奶牛。每头牛以一定速度向右（$+x$ 方向）移动，该速度由移动 1 单位距离所需的整数时间 $r$ 描述。

FJ 并不满意他的奶牛在外赛跑而不在牛棚产奶。他计划在比赛结束后训斥参赛的奶牛。为了确定哪些奶牛参赛，FJ 站在 $(0, 0)$ 处并沿 $+y$ 方向的射线观察。当一头牛在某个时刻成为这条射线上首个可见的牛时，FJ 就会看到它。如果一头牛在穿过 FJ 视线期间始终被其他牛"挡住"，则她不可见。

请计算 FJ 在整个比赛过程中能看到的奶牛数量。

输入格式

第一行包含 $N$。接下来 $N$ 行每行描述一头牛，包含三个整数 $x$ $y$ $r$，分别表示：左端点初始坐标为 $(x, y)$，以每移动 1 单位距离需要 $r$ 单位时间的速度向右移动。$x$ 的取值范围为 $-1000$ 到 $-1$，$y$ 的取值范围为 $1$ 到 $1,000,000$（所有牛的 $y$ 值互不相同以避免碰撞），$r$ 的取值范围为 $1$ 到 $1,000,000$。

输出格式

一个整数，表示 FJ 能看到的奶牛数量。

输入输出样例 1

3 
-2 1 3 
-3 2 3 
-5 100 1

2

说明/提示

FJ 可以看到牛 1 和 2，但看不到牛 3。