Nearest Excluded Points (Codeforces 1651D)
Tags: Others, shortest paths

You are given $$$n$$$ distinct points on a plane. The coordinates of the $$$i$$$-th point are $$$(x_i, y_i)$$$.For each point $$$i$$$, find the nearest (in terms of Manhattan distance) point with integer coordinates that is not among the given $$$n$$$ points. If there are multiple such points — you can choose any of them.The Manhattan distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is $$$|x_1 - x_2| + |y_1 - y_2|$$$.

Input: The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of points in the set.The next $$$n$$$ lines describe points. The $$$i$$$-th of them contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 2 \cdot 10^5$$$) — coordinates of the $$$i$$$-th point.It is guaranteed that all points in the input are distinct.

Output: Print $$$n$$$ lines. In the $$$i$$$-th line, print the point with integer coordinates that is not among the given $$$n$$$ points and is the nearest (in terms of Manhattan distance) to the $$$i$$$-th point from the input.Output coordinates should be in range $$$[-10^6; 10^6]$$$. It can be shown that any optimal answer meets these constraints.If there are several answers, you can print any of them.


Sample Inputs:
6
2 2
1 2
2 1
3 2
2 3
5 5

8
4 4
2 4
2 2
2 3
1 4
4 2
1 3
3 3

Sample Outputs:
1 1
1 1
2 0
3 1
2 4
5 4

4 3
2 5
2 1
2 5
1 5
4 1
1 2
3 2

Solution (Python):
import collections
import sys

def _input_iter():
    for line in sys.stdin:
        for part in line.strip().split(' '):
            stripped = part.strip()
            if stripped:
                yield stripped
stream = _input_iter()

def read_int():
    return int(next(stream))

def read_str():
    return next(stream)

def neighbors(p):
    return [(p[0] + 1, p[1]), (p[0] - 1, p[1]), (p[0], p[1] + 1), (p[0], p[1] - 1)]

def run():
    n = read_int()
    points = []
    point_set = set()
    for _ in range(n):
        p = (read_int(), read_int())
        points.append(p)
        point_set.add(p)
    ans = {}
    q = collections.deque()
    for p in points:
        for pn in neighbors(p):
            if pn not in point_set:
                q.append(p)
                ans[p] = pn
                break
    while q:
        p = q.popleft()
        for pn in neighbors(p):
            if pn in point_set and pn not in ans:
                q.append(pn)
                ans[pn] = ans[p]
    for p in points:
        print(*ans[p])

def main():
    run()
if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def get_neighbors(cord):
    (x, y) = cord
    return [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]

def solve(points):
    point_is_present = set()
    for p in points:
        point_is_present.add(p)
    bfs_list = deque()
    dist = {}
    for p in points:
        surrounded = True
        neighbors = get_neighbors(p)
        for neigbor in neighbors:
            if neigbor not in point_is_present:
                surrounded = False
                dist[p] = neigbor
                bfs_list.append(p)
                break
    while len(bfs_list) > 0:
        p = bfs_list.popleft()
        ans = dist[p]
        neighbors = get_neighbors(p)
        for neigbor in neighbors:
            if neigbor in point_is_present:
                if neigbor not in dist:
                    dist[neigbor] = ans
                    bfs_list.append(neigbor)
    for p in points:
        (x, y) = dist[p]
        print(x, y)
if __name__ == '__main__':
    n = int(input())
    points = []
    for i in range(n):
        (x, y) = map(int, input().split())
        points.append((x, y))
    solve(points)

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

def solve(n, arr):
    included = set(arr)
    ans = {}
    dq = deque()
    for (x, y) in arr:
        for (nx, ny) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if (nx, ny) not in included:
                ans[x, y] = (nx, ny)
                dq.append((x, y))
    while dq:
        (x, y) = dq.popleft()
        for (nx, ny) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if (nx, ny) in included and (nx, ny) not in ans:
                ans[nx, ny] = ans[x, y]
                dq.append((nx, ny))
    for (x, y) in arr:
        print(*ans[x, y])
n = int(input())
arr = list([tuple(map(int, input().split())) for _ in range(n)])
solve(n, arr)