#5213. Problem 3. Mountain View

0

Problem 3. Mountain View

Problem 3. Mountain View

USACO 2019 January Contest, Silver

从农场里奶牛Bessie的牧草地向远端眺望,可以看到巍峨壮丽的山脉绵延在地平线上。山脉里由NN座山峰(1N1051 \leq N \leq 10^5)。如果我们把Bessie的视野想象成xyxy平面,那么每座山峰都是一个底边在xx轴上的三角形。山峰的两腰均与底边成45度角,所以山峰的峰顶是一个直角。于是山峰ii可以由它的峰顶坐标(xi,yi)(x_i, y_i)精确描述。没有两座山峰有完全相同的峰顶坐标。

Bessie尝试数清所有的山峰,然而由于它们几乎是相同的颜色,所以如果一座山峰的峰顶在另一座山峰的三角形区域的边界上或是内部,她就无法看清。

请求出Bessie能够看见的不同的山峰的峰顶的数量,也就是山峰的数量。

输入格式(文件名:mountains.in):

输入的第一行包含NN。以下NN行每行包含xix_i0xi1090 \leq x_i \leq 10^9)和yiy_i1yi1091 \leq y_i \leq 10^9),描述一座山峰的峰顶的坐标。

输出格式(文件名:mountains.out):

输出Bessie能够分辨出的山峰的数量。

输入格式:


3
4 6
7 2
2 5

输出格式:


2

在这个例子中,Bessie能够看见第一座和最后一座山峰。第二座山峰被第一座山峰掩盖了。

供题:Brian Dean