#HF20243. 蛋糕识别(cake)
蛋糕识别(cake)
No testdata at current.
题目描述
在学习人工智能课程后,小肥对“图像识别”技术特别着迷。课后,小肥下载了一个 能识别蛋糕的开源软件。该软件能将图像中所有蛋糕,识别为底部沿着x轴的等腰角形 (如图1所示)。

如果一块蛋糕的顶点 ..不在另一块蛋糕 (包括其他蛋糕边界) 之内,那么就可以被识别 出来。例如,在图1中可以识别出2块蛋糕。由于软件还在完善过程中,若有多块蛋糕顶 点的x轴坐标相同且高度(y轴坐标)一致,这些重叠在一起的蛋糕都无法被识别出来。
在一张图片中共有n块蛋糕,小肥已标注出所有蛋糕顶点的x轴和y轴坐标,请计算 出该软件能识别出其中多少块蛋糕。
输入格式
从文件cake.in 中读入数据。
输入的第一行包含一个正整数n,表示蛋糕的总数量。
接下来n行,每行包含2个用空格分隔的正整数xi和yi。表示第i块蛋糕顶点的x轴 坐标和y轴坐标。
输出格式
输出到文件cake.out 中。
输出一行,其中包含一个整数,代表软件能识别出的蛋糕数量。
输入输出样例
输入样例1:
5
5 4
1 2
2 2
1 2
6 3
输出样例1:
2
输出样例1解释:

如图2所示,软件可以识别出顶点坐标为(2, 2)、(5, 4)这两块蛋糕,而顶点坐标为(6, 3) 的蛋糕由于顶点在(5, 4)这块蛋糕内,故无法被识别出来;同样顶点坐标为 (1, 2)的两块重 叠蛋糕也无法识别出来。
数据范围
对于所有测试数据,保证:1≤n≤10^5,1≤xi, yi≤10^5。
| 测试点编号 | n≤ | xi, yi |
|---|---|---|
| 1-4 | 100 | 1≤xi, yi≤100 |
| 5-8 | 1000 | 1≤xi, yi≤10000 |
| 9-12 | 10000 | 1≤xi, yi≤30000 |
| 13-16 | 50000 | 1≤xi, yi≤60000 |
| 17-20 | 10^5 | 1≤xi, yi≤10^5 |