AT_abc225_e.[ABC225E] フ

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在二维平面第一象限上有 $N$ 个“フ”字形。

第 $i$ 个“フ”字形（ $1 \leq i \leq N$ ）由两条线段组成，分别连接 $(x_i-1, y_i)$ 与 $(x_i, y_i)$ ，以及 $(x_i, y_i-1)$ 与 $(x_i, y_i)$ 。

你可以从这 $N$ 个“フ”字形中选择 $0$ 个或多个进行删除。

请问，经过适当选择要删除的“フ”字形后，从原点能够完整看到的“フ”字形的最大数量是多少？

这里，从原点能够完整看到某个“フ”字形（记为第 $i$ 个）的充要条件如下：

以原点、 $(x_i-1, y_i)$ 、 $(x_i, y_i)$ 、 $(x_i, y_i-1)$ 为顶点的四边形的内部（不包括边界）与其他任何“フ”字形没有公共部分。

输入格式

输入按以下格式从标准输入读入。

$N$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_N\ y_N$

输出格式

输出从原点能够完整看到的“フ”字形的最大数量。

输入输出样例

输入#1
```
3
1 1
2 1
1 2
```
输出#1
```
2
```

输入#2

10
414598724 87552841
252911401 309688555
623249116 421714323
605059493 227199170
410455266 373748111
861647548 916369023
527772558 682124751
356101507 249887028
292258775 110762985
850583108 796044319

输出#2

说明/提示

限制条件

$1 \leq N \leq 2 \times 10^5$
$1 \leq x_i, y_i \leq 10^9$
$(x_i, y_i) \neq (x_j, y_j)\ (i \neq j)$
所有输入均为整数

样例解释 1

当删除第 $1$ 个“フ”字形时，从原点可以看到第 $2$ 个和第 $3$ 个“フ”字形，共 $2$ 个，这是最大值。如果一个都不删，则从原点只能看到第 $1$ 个“フ”字形。

样例解释 2

不删除任何“フ”字形是最优的选择。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页