AT_arc065_c.[ARC065E] へんなコンパス

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

在 $xy$ 平面上有 $N$ 个洞。第 $i$ 个洞的位置为 $(x_i, y_i)$ 。

第 $i$ 个洞和第 $j$ 个洞之间的曼哈顿距离记作 $d(i, j) = |x_i - x_j| + |y_i - y_j|$ 。

你有一个“曼哈顿指南针”。这个指南针总是指向两个洞。指南针指向第 $p$ 个洞和第 $q$ 个洞，与指向第 $q$ 个洞和第 $p$ 个洞是没有区别的。

此外，如果 $d(p, q) = d(p, r)$ ，那么当指南针指向第 $p$ 个洞和第 $q$ 个洞时，你可以将其移动为指向第 $p$ 个洞和第 $r$ 个洞。

最开始，指南针指向第 $a$ 个洞和第 $b$ 个洞。请你求出指南针最终能够指向的不同洞的组合数。

输入格式

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

$N$ $a$ $b$ $x_1$ $y_1$ : $x_N$ $y_N$

输出格式

输出指南针最终能够指向的不同洞的组合数。

输入输出样例

输入#1
```
5 1 2
1 1
4 3
6 1
5 5
4 8
```
输出#1
```
4
```
输入#2
```
6 2 3
1 3
5 3
3 5
8 4
4 7
2 5
```
输出#2
```
4
```
输入#3
```
8 1 2
1 5
4 3
8 2
4 7
8 8
3 3
6 6
4 8
```
输出#3
```
7
```

说明/提示

限制条件

$2 \leq N \leq 10^5$
$1 \leq x_i, y_i \leq 10^9$
$1 \leq a < b \leq N$
当 $i \neq j$ 时， $(x_i, y_i) \neq (x_j, y_j)$
$x_i, y_i$ 均为整数

样例解释 1

最开始，指南针指向洞 $1, 2$ 。由于 $d(1,2) = d(1,3)$ ，所以可以指向洞 $1, 3$ 。又因为 $d(1,3) = d(3,4)$ ，所以可以指向洞 $3, 4$ 。又因为 $d(1,2) = d(2,5)$ ，所以可以指向洞 $2, 5$ 。没有其他洞的组合可以被指南针指向，因此答案为 $4$ 。

由 ChatGPT 4.1 翻译

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

首页