Problem:
 Score : 900 points    Problem Statement There are N pinholes on the xy -plane. The i -th pinhole is located at (x_i,y_i) .  We will denote the Manhattan distance between the i -th and j -th pinholes as d(i,j)(=|x_i-x_j|+|y_i-y_j|) .  You have a peculiar pair of compasses, called Manhattan Compass .
This instrument always points at two of the pinholes.
The two legs of the compass are indistinguishable, thus we do not distinguish the following two states: the state where the compass points at the p -th and q -th pinholes, and the state where it points at the q -th and p -th pinholes.  When the compass points at the p -th and q -th pinholes and d(p,q)=d(p,r) , one of the legs can be moved so that the compass will point at the p -th and r -th pinholes.  Initially, the compass points at the a -th and b -th pinholes.
Find the number of the pairs of pinholes that can be pointed by the compass.      Constraints  2≦N≦10^5  1≦x_i, y_i≦10^9  1≦a < b≦N  When i ≠ j , (x_i, y_i) ≠ (x_j, y_j)  x_i and y_i are integers.         Input The input is given from Standard Input in the following format:  N  a  b  x_1  y_1 : x_N  y_N       Output Print the number of the pairs of pinholes that can be pointed by the compass.        Sample Input 1 5 1 2
1 1
4 3
6 1
5 5
4 8      Sample Output 1 4  Initially, the compass points at the first and second pinholes.  Since d(1,2) = d(1,3) , the compass can be moved so that it will point at the first and third pinholes.  Since d(1,3) = d(3,4) , the compass can also point at the third and fourth pinholes.  Since d(1,2) = d(2,5) , the compass can also point at the second and fifth pinholes.  No other pairs of pinholes can be pointed by the compass, thus the answer is 4 .       Sample Input 2 6 2 3
1 3
5 3
3 5
8 4
4 7
2 5      Sample Output 2 4       Sample Input 3 8 1 2
1 5
4 3
8 2
4 7
8 8
3 3
6 6
4 8      Sample Output 3 7

Solution (Python):
import bisect
import sys
from collections import defaultdict


class RandomizedBinarySearchTree:
    def __init__(self):
        self.children = [[-1], [-1]]
        self.values = [0]
        self.counts = [0]
        self.root = 0

    def merge(self, left_root, right_root):
        children = self.children
        counts = self.counts
        li = left_root
        ri = right_root
        stack = []
        switch = 0
        while li != 0 and ri != 0:
            if switch:
                stack.append((li, 1))
                li = children[1][li]
            else:
                stack.append((ri, 0))
                ri = children[0][ri]
            switch ^= 1

        i = li if li != 0 else ri
        while stack:
            pi, is_right = stack.pop()
            children[is_right][pi] = i
            counts[pi] = counts[children[0][pi]] + counts[children[1][pi]] + 1
            i = pi

        return i

    def split(self, root, x):
        i = root
        lefts, rights = self.children
        values = self.values
        counts = self.counts
        l_stack = []
        r_stack = []
        while i != 0:
            if x < values[i]:
                r_stack.append(i)
                i = lefts[i]
            else:
                l_stack.append(i)
                i = rights[i]

        li, ri = 0, 0
        while l_stack:
            pi = l_stack.pop()
            rights[pi] = li
            counts[pi] = counts[lefts[pi]] + counts[li] + 1
            li = pi
        while r_stack:
            pi = r_stack.pop()
            lefts[pi] = ri
            counts[pi] = counts[ri] + counts[rights[pi]] + 1
            ri = pi

        return li, ri

    def insert(self, x):
        ni = len(self.values)
        self.children[0].append(0)
        self.children[1].append(0)
        self.values.append(x)
        self.counts.append(1)

        li, ri = self.split(self.root, x)
        self.root = self.merge(self.merge(li, ni), ri)

    def delete(self, x):
        li, mri = self.split(self.root, x - 1)
        mi, ri = self.split(mri, x)

        if mi == 0:
            self.root = self.merge(li, ri)
            return

        self.root = self.merge(li, ri)
        return

    def upper_bound(self, x, default=-1):
        i = self.root
        lefts, rights = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != 0:
            if x < values[i]:
                y = values[i]
                c = j + counts[lefts[i]]
                i = lefts[i]
            else:
                j += counts[lefts[i]] + 1
                i = rights[i]
        return y, c

    def lower_bound(self, x, default=-1):
        i = self.root
        lefts, rights = self.children
        values = self.values
        counts = self.counts
        y = default
        c = counts[i]
        j = 0
        while i != 0:
            if x <= values[i]:
                y = values[i]
                c = j + counts[lefts[i]]
                i = lefts[i]
            else:
                j += counts[lefts[i]] + 1
                i = rights[i]
        return y, c

    def get_k_th(self, k, default=-1):
        i = self.root
        children = self.children
        values = self.values
        counts = self.counts
        if counts[i] <= k:
            return default
        j = k
        while i != 0:
            left_count = counts[children[0][i]]
            if left_count == j:
                return values[i]
            elif left_count > j:
                i = children[0][i]
            else:
                j -= left_count + 1
                i = children[1][i]
        return default

    def debug_print(self):
        print('Lefts ', self.children[0])
        print('Rights', self.children[1])
        print('Values', self.values)
        print('Counts', self.counts)
        self._debug_print(self.root, 0)

    def _debug_print(self, i, depth):
        if i != -1:
            self._debug_print(self.children[0][i], depth + 1)
            print('      ' * depth, self.values[i], self.counts[i])
            self._debug_print(self.children[1][i], depth + 1)


def x_check(x_dict, nx, y, d, stack, stacked):
    counter = 0
    if nx in x_dict:
        rbst, lst = x_dict[nx]
        ny, _ = rbst.lower_bound(y - d, y + d + 1)
        while ny <= y + d:
            z = (nx << 32) | ny
            if z not in stacked:
                stack.append(z)
                stacked.add(z)
            rbst.delete(ny)
            ny, _ = rbst.lower_bound(y - d, y + d + 1)
        i = bisect.bisect_left(lst, y - d)
        j = bisect.bisect(lst, y + d)
        counter = j - i
    return counter


def y_check(y_dict, ny, x, d, stack, stacked):
    counter = 0
    if ny in y_dict:
        rbst, lst = y_dict[ny]
        nx, _ = rbst.lower_bound(x - d, x + d + 1)
        while nx <= x + d:
            z = (nx << 32) | ny
            if z not in stacked:
                stack.append(z)
                stacked.add(z)
            rbst.delete(nx)
            nx, _ = rbst.lower_bound(x - d, x + d + 1)
        i = bisect.bisect(lst, x - d)
        j = bisect.bisect_left(lst, x + d)
        counter = j - i
    return counter


n, a, b, *xy = map(int, sys.stdin.buffer.read().split())
xxx = xy[0::2]
yyy = xy[1::2]

x_dict = defaultdict(lambda: [RandomizedBinarySearchTree(), []])
y_dict = defaultdict(lambda: [RandomizedBinarySearchTree(), []])
OFFSET = 10 ** 9
MASK = (1 << 32) - 1
for i in range(n):
    x = xxx[i] - yyy[i] + OFFSET
    y = xxx[i] + yyy[i]
    x_dict[x][0].insert(y)
    y_dict[y][0].insert(x)
    x_dict[x][1].append(y)
    y_dict[y][1].append(x)

for _, lst in x_dict.values():
    lst.sort()
for _, lst in y_dict.values():
    lst.sort()

a -= 1
b -= 1
ax_, ay_ = xxx[a], yyy[a]
bx_, by_ = xxx[b], yyy[b]
ax, ay = ax_ - ay_ + OFFSET, ax_ + ay_
bx, by = bx_ - by_ + OFFSET, bx_ + by_
az = (ax << 32) | ay
bz = (bx << 32) | by
d = max(abs(ax - bx), abs(ay - by))
x_dict[ax][0].delete(ay)
x_dict[bx][0].delete(by)
y_dict[ay][0].delete(ax)
y_dict[by][0].delete(bx)

stack = [az, bz]
stacked = {az, bz}
ans = 0
while stack:
    z = stack.pop()
    y = z & MASK
    x = z >> 32
    ans += x_check(x_dict, x - d, y, d, stack, stacked)
    ans += x_check(x_dict, x + d, y, d, stack, stacked)
    ans += y_check(y_dict, y - d, x, d, stack, stacked)
    ans += y_check(y_dict, y + d, x, d, stack, stacked)

print(ans // 2)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict
import bisect

INF = 10 ** 12

N,a,b = map(int,input().split())
X_to_Y = defaultdict(lambda: [-INF,INF])
Y_to_X = defaultdict(lambda: [-INF,INF])
for i in range(1,N+1):
    x,y = map(int,input().split())
    x,y = x+y,x-y
    X_to_Y[x].append(y)
    Y_to_X[y].append(x)
    if i == a:
        sx,sy = x,y
    elif i == b:
        tx,ty = x,y

R = max(abs(sx-tx), abs(sy-ty))

for key, arr in X_to_Y.items():
    arr.sort()
    L = len(arr)
    move_right = list(range(1,L)) + [None]
    X_to_Y[key] = [arr,move_right]
    
for key, arr in Y_to_X.items():
    arr.sort()
    L = len(arr)
    move_right = list(range(1,L)) + [None]
    Y_to_X[key] = [arr,move_right]

equiv_class = set([(sx,sy), (tx,ty)])

answer = 0
task = [(sx,sy), (tx,ty)]

while task:
    x,y = task.pop()
    
    
    
    for x1 in [x-R,x+R]:
        if not (x1 in X_to_Y):
            continue
        arr, move_right = X_to_Y[x1]
        left = bisect.bisect_left(arr, y-R)
        right = bisect.bisect_right(arr, y+R)
        
        answer += right - left 
        i = left
        while i < right:
            y1 = arr[i]
            if (x1,y1) not in equiv_class:
                equiv_class.add((x1,y1))
                task.append((x1,y1))
            
            next_i = move_right[i]
            if next_i >= right:
                break
            move_right[i] = right
            i = next_i
    for y1 in [y-R,y+R]:
        if not y1 in Y_to_X:
            continue
        arr, move_right = Y_to_X[y1]
        left = bisect.bisect_left(arr, x-R+1)
        right = bisect.bisect_right(arr, x+R-1)
        
        answer += right - left 
        i = left
        while i < right:
            x1 = arr[i]
            if (x1,y1) not in equiv_class:
                equiv_class.add((x1,y1))
                task.append((x1,y1))
            
            next_i = move_right[i]
            if next_i >= right:
                break
            move_right[i] = right
            i = next_i

answer //= 2 
print(answer)

Solution (Python):
N, a, b = map(int, input().split()); a -= 1; b -= 1
P = []
Q = []
for i in range(N):
    x, y = map(int, input().split())
    P.append((x-y, x+y, i))
    Q.append((x+y, x-y, i))

d = max(abs(P[a][0] - P[b][0]), abs(P[a][1] - P[b][1]))

*parent, = range(N)
def root(x):
    if x == parent[x]:
        return x
    y = parent[x] = root(parent[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px < py:
        parent[py] = px
    else:
        parent[px] = py
C = [0]*N
D = [0]*N

def check(P0, i0, j0):
    return abs(P0[i0][0] - P0[j0][0]) == abs(P0[i0][1] - P0[j0][1])

def solve(P0):
    P = P0[:]
    P.sort()

    s = t = 0; prev = -1
    for i in range(N):
        x, y, i0 = P[i]
        while t < N and P[t][0] < x-d or (P[t][0] == x-d and P[t][1] <= y+d): t += 1
        while s < N and (P[s][0] < x-d or (P[s][0] == x-d and P[s][1] < y-d)): s += 1
        if s < t:
            j0 = P[s][2]
            unite(i0, j0)
            if check(P0, i0, j0):
                D[i0] += 1
            else:
                C[i0] += 1
            if s < t-1:
                j0 = P[t-1][2]
                if check(P0, i0, j0):
                    D[i0] += 1
                    C[i0] += t-s-2
                else:
                    C[i0] += t-s-1
            for j in range(max(prev, s), t-1):
                unite(P[j][2], P[j+1][2])
            prev = t-1
solve(P)
solve(Q)

S = T = 0
r = root(a)
for i in range(N):
    if root(i) == r:
        S += C[i]; T += D[i]
print(S + T//2)