传统题 1000ms 256MiB

蛋糕识别

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

在学习人工智能课程后,小肥对“图像识别”技术特别着迷。课后,小肥下载了一个能识别蛋糕的开源软件。该软件能将图像中所有蛋糕,识别为底部沿着 xx 轴的 等腰直角三角形(如图 1 所示)。

如果一块蛋糕的 顶点 不在另一块蛋糕 (包括其他蛋糕边界) 之内,那么就可以被识别出来。例如,在图 1 中可以识别出 22 块蛋糕。由于软件还在完善过程中,若有多块蛋糕顶点的 xx 轴坐标相同且高度(yy 轴坐标)一致,这些重叠在一起的蛋糕都无法被识别出来。

在一张图片中共有 nn 块蛋糕,小肥已标注出所有蛋糕顶点的 xx 轴和 yy 轴坐标,请计算出该软件能识别出其中多少块蛋糕。

输入格式

输入的第一行包含一个正整数 nn,表示蛋糕的总数量。

接下来 nn 行,每行包含 22 个用空格分隔的正整数 xix_iyiy_i。表示第 ii 块蛋糕顶点的 xx 轴坐标和 yy 轴坐标。

输出格式

输出一行,其中包含一个整数,代表软件能识别出的蛋糕数量。

样例输入1

5
5 4
1 2
2 2
1 2
6 3

样例输出1

2

说明

对于样例 2,32,3,请在文件中下载。

对于样例 11

如图 2 所示,软件可以识别出顶点坐标为 (2,2)(2, 2)(5,4)(5, 4) 这两块蛋糕,而顶点坐标为 (6,3)(6, 3) 的蛋糕由于顶点在 (5,4)(5, 4) 这块蛋糕内,故无法被识别出来;同样顶点坐标为 (1,2)(1, 2) 的两块重叠蛋糕也无法识别出来。

数据范围与规模

对于所有测试数据,保证:1n1051\le n\le 10^51xi,yi1051\le x_i, y_i\le 10^5

测试点编号 nn\le xi,yix_i,y_i
141\sim 4 100100 1xi,yi1001\le x_i, y_i\le 100
585\sim 8 10001000 1xi,yi100001\le x_i, y_i\le 10000
9129\sim 12 1000010000 1xi,yi300001\le x_i, y_i\le 30000
131613\sim 16 5000050000 1xi,yi600001\le x_i, y_i\le 60000
172017\sim 20 10510^5 1xi,yi1051\le x_i, y_i\le 10^5

CSP-J/S 公开训练(第一场)

未参加
状态
已结束
规则
IOI
题目
6
开始于
2025-6-26 9:00
结束于
2025-7-8 21:00
持续时间
300 小时
主持人
参赛人数
38