AtCoder Regular Contest 065 - Manhattan Compass

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-----
5 1 2
1 1
4 3
6 1
5 5
4 8

-----Sample Output-----
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.

Difficulty: VERY_HARD

Starter code:

Solutions:
(N, a, b) = list(map(int, input().split()))
a -= 1
b -= 1
P = []
Q = []
for i in range(N):
	(x, y) = list(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,) = list(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)


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)


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)