分数: 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