UOJ Logo 蜗牛编程训练题库

JZOJ

#1118. 【usaco2019jan_silver_T3】 Mountain View

统计
时间限制:1s    空间限制:256MB    输入文件:mountains.in    输出文件:mountains.out
当前24小时内您还剩30次提交本题的机会

题目描述

从农场里奶牛Bessie的牧草地向远端眺望,可以看到巍峨壮丽的山脉绵延在地平线上。山脉里由N座山峰($1≤N≤10^5$)。如果我们把Bessie的视野想象成xy平面,那么每座山峰都是一个底边在x轴上的三角形。山峰的两腰均与底边成45度角,所以山峰的峰顶是一个直角。于是山峰i可以由它的峰顶坐标(xi,yi)精确描述。没有两座山峰有完全相同的峰顶坐标。 Bessie尝试数清所有的山峰,然而由于它们几乎是相同的颜色,所以如果一座山峰的峰顶在另一座山峰的三角形区域的边界上或是内部,她就无法看清。

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

输入格式

输入的第一行包含N。

以下N行每行包含xi(0≤xi≤10^9)和yi(1≤yi≤10^9),描述一座山峰的峰顶的坐标。

输出格式

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

样例数据

input

3
4 6
7 2
2 5

output

2

说明

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

数据规模与约定

时间限制:$1 \text {s}$

空间限制:$256 \text {MB}$

解题讨论区

标题 发表者 发表日期