Mountain View

题目描述

在农场的牧场里，奶牛 Bessie 可以远眺地平线上的一片山脉。山脉中共有 $N$ 座山（$1 \leq N \leq 10^5$）。如果把 Bessie 的视野看作 $xy$ 平面，那么每座山都是一个底边落在 $x$ 轴上的三角形。山的两条边与底边都成 45 度角，因此山峰处形成一个直角。

因此，第 $i$ 座山可以由其山峰的位置 $(x_i, y_i)$ 精确描述。任意两座山的山峰位置都不完全相同。

Bessie 试图数清所有的山，但由于它们颜色大致相同，如果某座山的山峰位于另一座山的三角形区域的边界上或内部，她就无法看到这座山。

请确定 Bessie 能看到的不同山峰（因此也就是山）的数量。

输入格式

第一行输入包含 $N$。接下来的 $N$ 行中，每行包含 $x_i$（$0 \leq x_i \leq 10^9$）和 $y_i$（$1 \leq y_i \leq 10^9$），描述一座山的山峰位置。

输出格式

请输出 Bessie 能够区分的山的数量。

3
4 6
7 2
2 5

2

提示

在这个例子中，Bessie 能看到第一座和最后一座山。第二座山被第一座山遮挡。

题目来源：Brian Dean

标签: USACO|2019|Silver

来源

USACO|2019|Silver