← 返回题目列表

AtCoder · arc065_c

E. 曼哈顿指南针

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

有 N 上有针孔 xy- 平面。 i第一个针孔位于 (x_i,y_i).

我们将表示之间的曼哈顿距离 i-th 和 j第一个针孔为 d(i,j)(=|x_i-x_j|+|y_i-y_j|).

你有一副奇特的圆规,叫做 曼哈顿指南针。 该仪器始终指向其中两个针孔。 指南针的两条腿是无法区分的,因此我们不区分以下两种状态: 指南针指向的状态 p-th 和 q第一个针孔,以及它指向的状态 q-th 和 p第一个针孔。

当指南针指向 p-th 和 q第一个针孔和 d(p,q)=d(p,r),可以移动其中一条腿,使指南针指向 p-th 和 r第一个针孔。

最初,指南针指向 a-th 和 b第一个针孔。 求指南针可以指向的针孔对的数量。

约束

  • 2≦N≦10^5
  • 1≦x_i, y_i≦10^9
  • 1≦a < b≦N
  • 当 i ≠ j, (x_i, y_i) ≠ (x_j, y_j)
  • x_i 和 y_i 是整数。

输入

输入由标准输入按以下格式给出:

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

最初,指南针指向第一个和第二个针孔。

自从 d(1,2) = d(1,3),可以移动指南针,使其指向第一个和第三个针孔。

自从 d(1,3) = d(3,4),指南针还可以指向第三个和第四个针孔。

自从 d(1,2) = d(2,5),指南针还可以指向第二个和第五个针孔。

指南针无法指向其他成对的针孔,因此答案是 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